Consequences of a Solution to NP Complete Problems?

m00nshyn3 asks: "If a person were to find a O(n) solution to an NP complete problem, it would obviously be a great advance in computer science, but what are the consequences of such a discovery? Would our most popular implementations of cryptography be useless overnight? It seems like there is a lot of immediate damage that could occur if such a solution were found. So if (when) the time comes, what is the responsible way for the solution to be made public?" If you had such an algorithm in hand, what could you do with it? It would be interesting to see how many problems we could map into the NP Complete model.

Comments

Salesman

[rusti999]

Salesmen will certainly be happy when such an algorithm is found. For other classes of NP-complete problems, check this book.

Unseen consequences!

[Lemmy Caution]

Analogously, if it was learned that eating Hostess Twinkies that had been marinated in thai green curry sauce while bathing gave one super-strength and x-ray vision, we would have to become gravely concerned about the possible rise of Thai-Twinkie-powered super-criminals who know what we look like in our Underoos. This is clearly something that man was not meant to know. Won't someone think of the children?

AI

[Trejus]

First off, if they found an O(n) algorithm, that means that all NP problems would be in linear time. I'm assuming the poster means O(n^t) where t is independent of n.

now if that were the case, i'd use it to build nifty AI's. Most ai problems are NP complete since they involve non-deterministically searching a problem space. Stuff like crossword puzzles and route planning come to mind for this one. Most of these problems do map to SAT, so it would be very short time before we start seeing some really intelligent AIs for a lot of your typical tasks.

Re:AI

[ChazeFroy]

Yes, all NP-problems would become solveable because they are all related. Many Computer Science programs have an Automata class, and they teach how to convert from one NP-complete problem to another.

Re:AI

[Nate Eldredge]

First off, if they found an O(n) algorithm, that means that all NP problems would be in linear time.

Not necessarily true. Remember, NP-complete means all NP problems can be reduced to it in polynomial time. So even if I found a O(n) solution to, say, Hamiltonian Path, it's quite possible that reducing (say) Traveling Salesman to Hamiltonian Path is not a linear-time reduction. It might be any polynomial, maybe n^5. In fact, the degree of the polynomial might depend on the kind of computer you have at hand (for instance, whether you have a random-access memory where you can access any word in constant time, or a tape where you have to wind through the whole thing to find the word you want.)

Re:AI

[cpeterso]

Who gives a shit, cockgoblin? A problem in polynomial, n>=2, time is not solvable in linear time, which is what the original poster was claimimg.


Discussing cockgoblins and polynomial equations in the same post makes my day. Thanks for the smile.

Is "harvardian" from Harvard? What does he know anyways..

Re:AI

[Trejus]

I assumed he meant that an O(n^t) solution with a very large value for t would be of theoretical interest but not have the kind of practical impact that he was thinking of. In other words, he meant O(n) or at least a relatively tractable O(n^t).

In essence you're right, an algo with a huge t would not be all that practical. However, once you have it down to poly time, it becomes relatively easy to get it into a more usable time space. I remember a lot of things from my datastructures class where the obvious solution was quadratic, with a little tweaking you got linear, and with some very convoluted code you got N/2 or better. I am not sure what that problem was (it may have been sorting), but that type of problem is pretty common. Despite that, for large problem spaces, the poly-time algo will be better than the exp-time algo.

Re:AI

[ghjm]

Symbols translated, what he's saying is: If they found a linear-time solution to NP, then NP problems would be solvable in linear time.

O(n) *means* linear time.

The actual quest is to prove that P=NP (or that P != NP), meaning any/all NP problems can be solved in O(P) where P represents any polynomial equation. Not O(n), whatever the article may say.

-Graham

Re:AI

[Fjord]

In addition to what the other poster stated, just because two problems are NP-Complete, it doesn't mean they have the same run-time. One problem can be thought to be O(n*e^n) and another O(e^n). Find a O(n) for the second, and the first maybe O(n^2). Note that then both are then in P. Finding a linear problem for one NP-complete problem with only bring all other problems into P. But some can still be O(n^1000).

Re:AI

[ajs]

Your definition of "intelligent" is suspect. I know many people who could pass Turing's test who would not be able to solve the NYT crossword. I don't think being able to solve hard problems quickly is a factor in intelligence. Being able to evaluate the relative quality of many options based on projected outcomes and prior experience is my rough stab at what makes up intelligence.

Interestingly there are many computer programs which perform this to a limited extent. We don't consider them "intelligent" for roughly the same reasons that we feel that tuna is an acceptable meal, but dolphins must be "safe"....

Re:AI

[Sir Tristam]

One of the problems you're probably thinking of is selecting the kth largest item out of a list of n items. If you do it by sorting the elements and selecting from the sorted list, then your worst-case bound is O(n lg n). However, there is a kth largest selection methodology that has a worst-case O(16n).

(And, no, before anybody asks, you can't use it to make a linear search by selecting the first largest, then second largest, etc. You'd have to perform the selection n times, so your worst case would be O(16n^2), much worse than O(n lg n).)

Chris Beckenbach

Re:AI

[Chris Burke]

Take an undergraduate course in AI and you'll see that when Computer Scientists talk about AI, they are generally talking about an entirely different set of problems than when a lay-person talks about AI.

With the effect that most undergraduates are very dissapointed after the first day of class, and half end up dropping the course. :)

Re:AI

[Chris Burke]

As was pointed out in another post (making this one redundant, moderators!) he is talking about the CS version of AI, not the popular notion of AI, and for that he's right -- a poly-time solution to NP problems would be incredibly helpfull.

err... what do you think?

[2Bits]

If you had such an algorithm in hand, what could you do with it?

Publish it as soon as possible, get credit for it, and rack up the monetary prize, don't you think? :)

Re:err... what do you think?

[rlowe69]

If you had such an algorithm in hand, what could you do with it?

I'd memorize it and then try to figure out how the guy did it ... ;)

Only the PK crypto

[color of static]

No we wouldn't see the whole crypto world come smashing down around us, but a large portion of it. All of the Public Key crypto would be reduced from an assumed set of hard problems to a set of simple ones. No more digital signatures, or communications without pre shared secrets. Although any system using just symmetric ciphers would be immune from this reduction in work effort.
Even if a timly NP complete solution is not found, PK based on factoring or discrete logarithms might get broken by other discoveries. For that reason I'm always watching the emergence of new PK systems such as FAPKC and some of the lattice based codes.

Re:Only the PK crypto

[harlows_monkeys]

I don't believe factoring is known to be NP-complete.

Re:Only the PK crypto

[logicnazi]

So wait is factoring in NP? OR is it that thing which is both NP and co-NP...I don't remember.

Either way P=NP doesnt seem to imply that there are no aysmetric function...just that there are no aysmetric polynomial time functions. There seems to be no theoretical reason why you couldn't build a PK system with an exponential encryption time and a super super exponential decryption time.

Secondly I am unsure if it even gets ride of polynomial time aysmetric functions. It puts a bound on how aysmetric they can be...as to whether this will mean a practical inability to do PK I don't know

Re:Only the PK crypto

[Zachary Kessin]

Factoring is not NP_Complete. There were some early public key cryptsystems that were NP complete but they were abandoned rather quickly. While the best general case solutions to NP-Complete are O(2^n) there are many specific case solutions that will solve some subset of problems much faster. Or will get close to the correct result quickly. In a crypto-system you want to make sure that it is hard to solve ALL posible cases not just the worst case senario.

Re:Only the PK crypto

[mikek]

Compositenesss is in NP (verify it easily by getting two factors and multiplying them together) so primality would then be in coNP. However, primality has also been shows to be in NP. If a language is NP-complete then its complement is coNP-complete. Since primality is in both NP and coNP, if it were NP-complete then that would imply that NP = coNP, which we don't believe is the case.

Re:Only the PK crypto

[color of static]

I think you are correct, but the complexity of NP-complete problems I believe set the upper bound of complexity for PK algorithms based on factoring and discrete logs.

Re:Only the PK crypto

[phliar]

No we wouldn't see the whole crypto world come smashing down around us, but a large portion of it.

Why?

Factoring is not known to be in NP or NP-complete

Re:Only the PK crypto

[Fnkmaster]

As the other responder said, nope. Factoring large pseudo-primes is not an NP-complete problem. For reference, see the RSA, Inc. FAQ - they clearly admit this. Or see any reasonable crypto textbook of the academic variety.

Re:Only the PK crypto

[Dr. Blue]

I hate to be harsh, but there is some of the most phenomenal crap posted on this story that I've seen on slashdot in a while. This is what I do guys, so let me clear up some things:

First, to all the people who keep saying "factoring isn't NP-complete" blah, blah, blah. That's not even a sensible question, since "factoring" isn't a decision problem. However, you *can* define a related decision problem that shows that if P=NP, then you can factor in polynomial time. So if indeed someone came up with an O(n) time algorithm for an NP-complete problem, then factoring would definitely be doable in polynomial time, and unless this were some really bizarre problem then factoring would most likely be pretty easy.

Second, factoring isn't the only thing that's affected here. If all problems in NP are efficiently solvable, then *all* cryptographic algorithms (public key or symmetric) are susceptible to known-plaintext attack. Meaning, if you know a plaintext and corresponding ciphertext, you can find the decryption key --- since that's always trivial to do with a public key algorithm (since you can create the ciphertext yourself), they'd all be easy to break.

So yes, public key crypto would cease to exist as we know it --- the only hope would be to find a function that's maybe O(n) to encrypt and Omega(n^10) to break, but an exponential time separation wouldn't be possible any more.

But symmetric key crypto would also be severely damaged as well.

Fortunately, most people think this is pretty unlikely!

Re:Only the PK crypto

[YoJ]

Factoring is not known to be NP-complete. Of course factoring is NP, since we can verify that a number is a factor of another by just dividing (which takes polynomial time). So factoring integers is not more difficult than any NP-complete problem. That said, even if someone discovered a polynomial time algorithm to solve NP-complete problems, the degree of the polynomial would probably be so big that it was useless in practice for any real problems with today's technology.

But the future of cryptography would be seriously shaken, since technology gets better and better, eventually the asymptotically faster methods will become the best way to do things. If the asymptotically fastest method is polynomial, then key lengths will have to get bigger faster and faster. Currently, increasing your key size by a X bits per year makes you immune to attack. But if there is a polynomial time attack, then suddenly the key size has to grow exponentially. Imagine doubling your key size every month.

I believe all cryptographic schemes are based on algorithms that are NP. Being NP means that the solution can be verified in polynomial time, but the solution cannot necessarily be found in polynomial time. The verification part is important to cryptography, since you have to be able to prove to other people that you can solve the problem (since you have the key).

I challenge anyone to name a cryptosystem that is not based on a problem that is NP.

Re:Only the PK crypto

[armb]

> Although any system using just symmetric ciphers would be immune from this reduction in work effort.

No. If you can non-deterministically guess the right symmetric key, checking it works is polynomial. (It isn't always possible to do the "check it works" step (e.g. for a one time pad), but for systems where a brute force search works at the moment, or would work in principle if the key wasn't so large it was impractical, it is).

Re:Only the PK crypto

[AME]

But that's not even an interesting case when talking about cryptography. You still need a secure channel on which to send your key. If you have such a channel then why are you not using that channel for your messages?

Unless you are using the same pad for all of your messages, in which case you have little hope of any real security.

Re:Only the PK crypto

[crawling_chaos]

It was interesting enough for the Soviets to use it as their main method when spying on the West. It's all a matter of how valuable the security of the message is. I believe that the US's nuclear launch codes are all one-time padded, for instance.

When the cost of a security breach is more expensive than couriering the keys, the one-time pad becomes very useful.

Re:Only the PK crypto

[AME]

I didn't say it wasn't useful. Merely that it wasn't cryptographically interesting. No more interesting than, say, the chance of guessing n numbers consecutively.

But the necessary preparation for one-time pads is too high for it to be generally useful for real-time secure communication.

If I had that O(n) algorithm...

[mfarah]

I'd release it to the public, then sit down until they hand me my well-deserved Turing award.

Seriously, there are more advantages (quick solutions to complex problems, like the traveller salesman) than disadvantages (cracking easily certain encryption mechanisms) to this.

But then again, my gut feeling is that P!=NP.

Re:If I had that O(n) algorithm...

[Peaker]

As someone already mentioned, the travelling salesman problem is about finding the *optimal* solution. For any practical purpose, a near-optimal solution can be found, and there are P solutions to this problem.
A certain P solution can be proven to always find a path at most twice the length of the optimal one.

Crypto is safe

[Nater]

Crypto algorithms are strong for other reasons. Factoring primes is not a difficult problem... the fastest known solution is already O(n), the reason it's time consuming is that you can choose arbitrarily large values of n, in which case, you need to do better than O(n) in order to effectively break it. One time pads are another thing altogether. There is no algorithm of any order that can break a proper OTP (note that an improper OTP, i.e. one who's pad is not truly random or who pad is reused could be cracked). Other algorithms are based on other principles, but in any case, most are based on mathematically difficult or impossible problems, not computationally difficult ones.

Re:Crypto is safe

[Nater]

(Nater pulls head out of ass, puts foot in mouth)

That should say "factoring large numbers" rather than "factoring primes"

My bad

Re:Crypto is safe

[Anonymous Coward]

Factoring is difficult. Remember that speed is normally expressed in terms of the size of the input. It only takes log n bits to represent n. Thus, a O(n) algorithm for factoring (where n is the input) is actually exponential in the input size.

I'm familiar with several fast primality testers, all probabilistic, but I'm not familiar with any fast factorization algorithm.

Re:Crypto is safe

[jsburke]

No, there's no O(n) algorithm for integer factorization. The fastest known deterministic algorithm just to test for primality runs in (lg n)^(O(lg lg lg n)) time, which is superpolynomial. Only randomized algorithms (i.e., ones that may produce the wrong answer) can achieve polynomial time.

Re:Crypto is safe

[AnotherBlackHat]

The problem is that most of the canonical methods of generating One Time Pads are based on discrete log (in the form of the Diffie-Helman (sp?) key exchange), which can be solved by factoring.

Are you on drugs? Most canonical methods of generating One Time Pads are based on physical processes, like throwing dice, sampling a radioactive source or digitizing lava lamps
Using a pseudo-random generator to generate one time pads offers pseudo security.

Re:Crypto is safe

[pthisis]

The problem is that most of the canonical methods of generating One Time Pads are based on discrete log (in the form of the Diffie-Helman (sp?) key exchange), which can be solved by factoring.

You're mixing things up. One-Time Pads are simply long strings of random numbers, you don't use Diffie-Hellman to generate them. And if you used DH to exchange them you defeat the point (which is that they're provably secure). They're generally delivered by trusted courier. OTPs are used (for instance) for some sensitive communications with US embassies and presumably by the CIA and NSA as well.

DH is completely unrelated to one time pads.

Sumner

Re:Crypto is safe

[RelliK]

Factoring primes is not a difficult problem... the fastest known solution is already O(n)

Oh, it's certainly not difficult. I can factor primes in O(1) time. Give me any prime and I'll tell you all its factors. However, the only known algorigthm to factor non-primes runs in exponential time. You got to love it when a clueless post gets marked "insightful" by even more clueless moderators.

Re:Crypto is safe

[Spy Hunter]

>Factoring primes is not a difficult problem... the fastest known solution is already O(n)

Oh yeah? I've got a nifty little program right here that will factor your large primes in O(1)! Don't believe me? Read it and weep!

int factor(int largePrime)
{
return largePrime;
}

Re:Crypto is safe

[Fjord]

However, the only known algorigthm to factor non-primes runs in exponential time

Yay! I just discovered a new algorithm! Take the number to be factored and call it n. Then, for i=2 to n/2, see if i divides n. This is much faster than exponential time.

You've got to love it when a clueless poster follows another clueless poster and tries to show how fucking great they are.

Re:Crypto is safe

[RelliK]

solution is O(b^n), where n is the size of the input and b is a constant

More specifically, b is the base of the number. (so it would be 2 for binary, 10 for decimal, etc.)

You have correctly explained that complexity of factoring a number is exponential in the the length of the number. That's because the magnitude of a number is exponential in its length for all bases other than one. Fjord used this little fact to claim that factoring a number is linear in the magnitude of the number. Well -- duh! Lame Fjord, really lame.

Thus factoring a 128-bit RSA key would not take c*128 time, for some constant c, as Fjord's post would seem to imply. It would take c*2^64 time, for some constant c. Why 64 and not 128? Theorem: any non-prime integer has a factor less than or equal to its square root. Proof: exercise to the reader (or take a first year algebra course).

Re:Crypto is safe

[haystor]

But you were correct in saying its not a difficult problem and that puts you way ahead of half the posts in this (or any) topic.

Re:Crypto is safe

[Nater]

Here's the brute force method for factorization that we all know and love:

Pick a positive integer, n. That's your input. Now, for each positive integer i less than n, find n % i. If that's 0, then i is a factor of n. That's a loop of n iterations which guarantees (hence it's an algorithm) that you'll find all the factors of n. And it's O(n).

Actually you only need to check up to the square root of n if you divide and test to see whether the result is an integer, because in that case you're finding factors two at a time and all the factors greater than the square root will be found by the time you get to the square root. Whether or not it's actually faster depends on implementation. Modulus and testing for 0 may or may not be more than half as fast as dividing and testing for an integer.

Re:Crypto is safe

[Nater]

Remember that speed is normally expressed in terms of the size of the input. It only takes log n bits to represent n.

Obviously when we're talking about computers, we can assume certain things, like that binary numbers will be used, but factorization is mathematics, not computers. You have to remember that in mathematics, you can slide the number base around and represent a given number using arbitrarily few digits. How do you write 1592 in base 1592? It's written like this: 10. So measuring the "size" of the number you're trying to factor by counting its digits is completely arbitrary. But since the integers are ordinal, we don't have to play this stupid "How should we measure this?" game. Integers measure themselves.

Remember, it's easy to factor a number. It can take an aweful long time, though, if your number is big.

Re:Crypto is safe

[Nater]

Although in some twisted fashion you can see it as being linear regarding the number to be factored

How is that so twisted? I think declaring a number's "size" to be equal to the number of digits needed to represent it is twisted. Number base and number of digits is purely cosmetic. Suppose I've got 32 bits of data that represent a number which is the composite of two primes. What do I know about those two primes before I do any calculations at all? They're both less than the number in my 32 bits. So the fact that it fits in 32 bits is pretty irrelevant to the algorithm. It's the number itself that matters.

Re:Crypto is safe

[Nater]

Where is the `incorrect' moderation option? Or `clueless poster' option?

People find this very hard to believe, but factorization is easy. The problem is that it can take a long time when the number your factoring is sufficiently large.

Think about the brute force factorization algorithm. Write it down, in fact. And now analyze it. You'll find that given a positive integer n to factor, the algorithm runs in O(n) time.

The reason cryptosystems based on factorization are thought to be safe is because we can choose arbitrarily large values of n and we presume that there is no more efficient way to factor integers. Now, if someone were to find a way to factor integers faster than O(n), we could still keep increasing n but that alone might not be sufficient. In any case, factorization is not an NP problem.

Re:Crypto is safe

[Florian Weimer]

I don't think so. Even if you know something is in O(n^t), you don't know the constant in the O. It might be so incredibly large that it doesn't make sense to use the O(n^t) algorithm.

On the other hand, in the distant future, we might reach a point where increasing the key length no longer increases security, but is probably very theoretical, too.

Re:Crypto is safe

[Nater]

Modulus ought to have similar running time to division. It's basically the same operation except for the last part where modulus returns the remainder and division returns the quotient. You could certainly implement modulus and division so that they're O(n), but I would be very surprised and a little pissed if there wasn't something better.

Re:Crypto is safe

[acidblood]

Ok, Mr. Know-it-all. Here's all the evidence I could gather for you. I really don't know why I spent so much time responding to an obvious troll, but it seems the moderators don't agree with me.

I hope that you realize, by the end of this post, that you shouldn't comment on subjects you have no clue about. Even worse, in this case, you have the wrong `clues'. You managed to squeeze a lot of stupid and wrong stuff in a few lines, and you seem to stick to you. So here goes:

factorization is easy

From the RSA Labs Cryptography FAQ (here's a link to this particular question):

Factoring is the underlying, presumably hard problem upon which several public-key cryptosystems are based, including the RSA algorithm. (...) It has not been proven that factoring must be difficult, and there remains a possibility that a quick and easy factoring method might be discovered, though factoring researchers consider this possibility remote.

Oh, then you must be wrong somewhere, OK? I know exactly where. Here's from the book ``Algorithms and Complexity'', by Herbert Wilf:

The problem is this. Let n be a given integer. We want to find out if n is prime. The method that we choose is the following. For each integer m = 2,3, ..., floor(sqrt(n)) we ask if m divides (evenly into) n. If all of the answers are `No,' then we declare n to be a prime number, else it is composite.

OK, so as a primality testing algorithm, it is rather inefficient. The Jacobi sum test and Atkin's test have a much better asymptotic growth, but if you look at it, you can use the same procedure to factor numbers.

We will now look at the computational complexity of this algorithm. That means that we are going to find out how much work is involved in doing the test. For a given integer n the work that we have to do can be measured in units of divisions of a whole number by another whole number. In those units, we obviously will do about sqrt(n) units of work.

See? Your O(n) algorithm (O(n) according to your stupid notation) is already a slow one. There are much faster algorithms out there than trial division. You should be realizing, by now, that you are beyond clueless, but here's the finishing touch:

It seems as though this is a tractable problem, because, after all, n is of polynomial growth in n. For instance, we do less than n units of work, and that's certainly a polynomial in n, isn't it? So, according to our definition of fast and slow algorithms, the distinction was made on the basis of polynomial vs. faster-than-polynomial growth of the work done with the problem size, and therefore this problem must be easy. Right? Well no, not really.

Reference to the distinction between fast and slow methods will show that we have to measure the amount of work done as a function of the number of bits of input to the problem. In this example, n is not the number of bits of input. For instance, if n = 59, we don't need 59 bits to describe n, but only 6. In general, the number of binary digits in the bit string of an integer n is close to (log n)/(log 2).

If we express the amount of work done as a function of B; we find that the complexity of this calculation is approximately 2**(B/2) , and that grows much faster than any polynomial function of B.

Satisfied there? Great. Now, if this book isn't enough for you, go out there and try to find another book which contradicts this one. And no, Teach Yourself Algorithms in 21 days, or something along these lines, doesn't count. Which seems to be your source of information; otherwise you'd have refrained from posting this.

Now, for the really stupid part:

The reason cryptosystems based on factorization are thought to be safe is because we can choose arbitrarily large values of n and we presume that there is no more efficient way to factor integers.

This shows how you have no understanding of asymptotics, or the general field of complexity of algorithms. Refer to the introduction of any good book on the matter, and you'll realize how wrong you are.

If that's not a good example, do some research on calculating Pi, for instance. You'll soon realize that the bottleneck for those computations is a means to do fast multiplication, and it can be done today in better than O(n log n) time (this particular value is the growth for the FFT-based methods.) But still, it can't be done yet in O(n) time, and it has been proven that this O(n) is the theoretical floor for a multiplication algorithm. So, it can't possibly do better than factorization, correct? But how come I can calculate a couple billion digits of Pi on my computer, while I can't factorize even a 100-digit number? In fact, I think I could hardly factorize an 80-digit number in the same amount of time it takes for calculating these billions of digits of Pi. (And it makes sense that algorithms for factorization are researched far more frequently than algorithms for Pi-calculation.)

Now, if you haven't convinced yourself, there's nothing more I can offer. I just hope the moderators read this post and mod you down into -1.

Now, if someone were to find a way to factor integers faster than O(n), we could still keep increasing n but that alone might not be sufficient.

I have shown you one such algorithm above. Did this change the world? No. And it is still a very slow algorithm by today's standards. Oh, and did I mention that it was invented by the greek mathematician Erathostenes, a few millenia ago? You should rethink about posting every idiot idea that comes out of your head from now on; at least avoid a complete embarassment by looking up whether you've been wrong for thousand of years.

Re:Crypto is safe

[oddjob]

I've read through your posts in this thread, and there is a consistent flaw in your reasoning that the other posters have not pointed out. Your argument for a O(n) algorithm assumes that division can be done in constant time, which is not the case. You don't get division for free. The algorithm for division is dependent on the magnitude of the numbers involved, regardless of base. (I don't recall the order of that algorithm... guess I could look it up :) )

Re:Crypto is safe

[acidblood]

which is that they're provably secure

You're mixing things up. OTPs are unconditionally secure. Shannon (in `Communication Theory of Secrecy Systems', 1949) has proven that unconditionally secure systems require keys as lenghty as the message itself, but OTOH an adversary cannot gleam anything about the plaintext given the ciphertext. One such example is the Vernam cipher, which represents the message and the key as a stream of bits, and XORs them together to generate the ciphertext.

Provably secure cryptosystems are those who have been proven to be as hard as the underlying hard problem, such as the Rabin cryptosystem, which is provably as hard as the integer factorization problem. In fact, it is based on the `square roots of modular numbers' problem, which has been proven to be computationally equivalent to integer factorization.

Just FYI.

Pizza and UPS Packages Would Arrive Faster

[Carnage4Life]

Considering that the Travelling Salesman Problem is NP complete and affects almost any problem that involves delivering something to several destinations in an optimal fashion. A solution to NP problems ould have widespread ramifications in improving many aspects of businesses that involve deliveries (including the airline business now that I think about it).

Re:Pizza and UPS Packages Would Arrive Faster

[isomeme]

Not really. While finding the optimal solution is NP-complete, for real world, non-contrived cases, getting a suboptimal-but-close-enough solution gets you within a few percent of peak perfomance. And for most real-world cases, there exist P algorithms which converge on a good enough solution quite rapidly.

Re:Pizza and UPS Packages Would Arrive Faster

[SpinyNorman]

Maybe that'd be true if Pizza Hut had a single guy to deliver ALL their pizzas (boy, would that job suck!), but in reality they use parallelism - multiple pizza deliverers that deliver a few pizzas on a simple route.

I pity the poor pizza boy who not only has to deliver pizzas to the entire United States, but maybe also has to wait for an O(google) (but not NP - whoopee!) algorithm to calculate his route before he can even start!

:-)

Re:Pizza and UPS Packages Would Arrive Faster

[SpinyNorman]

Consider dividing a 1000 house pizza delivery region by splitting it into a grid of 10x10 regions each containing an average of 10 houses.

N^1000 vs 100 * N^10 looks like a no brainer to me!

Now of course it's not optimal, but with a not too big, not too small grid it's going to be good enough, and if you can assign 10x10 pizza boys to the job they'll probably be done before the lone pizza delivery boy has even submitted the job to distributed.net

I'll give you the O(google) multiple snafu though!

With such an algorithm I would

[Density_Altitude]

be the king of MineSweeper

P=NP doesn't mean O(N)

[ElJefe]

Even if someone manages to prove that P=NP, it doesn't mean that a reasonably efficient solution can be found. All it means is that an NP-complete problem can be solved in polynomial time. That polynomial can still be huge, say N^1000. Except for really large N, current exponential-time algorithms could be superior to polynomial-time ones.

So, the short answer is that proving P=NP probably won't ruin your encryption. On the other hand, if someone did prove it, there will probably be a mad scramble to invent some new encryption schemes, just in case.

-Chris

O(n^x) is not necessarily hard...

[cmowire]

If you solve an NP complete problem in O(n^65535) time, you have just shown that P == NP. However, you still wouldn't be able to crack any of the NP complete problems that cryptography is based on in a reasonable amount of time.

Because trust me, if it was a low exponent for x, we'd have found it already. ;)

Besides, they'd just move to problems that are not NP complete for the popular cryptography algorythims. Cryptographers are too smart for their own good, you know.

Re:*sigh*

[kreyg]

Uh...

If only it was easy to find any decimal of PI with a simple formula, [blah blah]

Well, it almost is. Not decimal, precisely, but any arbitrary hex digit...

Ahem...

[RelliK]

Please take an algorithms course. It's taught in any university with a decent CS faculty. And if you think the course is too hard for you, feel free to come back and ask slashdot again. (Other questions may include: "what's a Turing Machine?" and "can you run Linux on it?")

As an aside, when did slashdot become a meta-search engine? Oh wait... never mind!

Here's a news flash

[empesey]

Would our most popular implementations of cryptography be useless overnight?

All of our cryptography schemes are made useless more often sooner than later.

Which is why I think this government initiative to install viruses on our computers is not only a bad idea, but an awful waste of money, that could be put into better use. Like an extra daisy-cutter or something.

Re:*sigh*

[Anonymous DWord]

Seriously. If you've got it, publish it (or not). Otherwise, why waste your time talking about it?

The obvious answer..

[mESSDan]

Is 42. ;)

RSA and all would *not* die

[JF]

Regardless of what was said above, this doesn't destroy public key cryptography at all. The two biggest mathematical assumptions used in PK crypto are that:

a) Factoring large numbers is hard
b) Solving discrete log problems is hard

Mind you, these are *not* NP-Complete problems (at the moment). They are believe to be in NP, but that's another story completly. Finding a polynomial algo for an NP-complete problem does not give you an algo for factoring and/or solving DLP problems.

Now on the other hand, if you had a quantum computer, you could factor in quadratic time, and solve DLPs in cubic time. Now *that* would be somewhat bad. :)

Re:RSA and all would *not* die

[JF]

Sorry, but you're basically wrong, and everyone here really needs a better understanding of complexity theory before posting.

Yeah, my thoughts exactly.

since NP-Complete problems are harder than NP-hard problems the other way around works

Huh huh... http://hissa.nist.gov/dads/HTML/nphard.html

I would really hate that!

[2Bits]

You know, when I look for an apartment, I look for something that does not have a pizza store near by. And I love to order pizza delivery from those chains that claim I can get it for free, if they can't deliver it within 30 minutes.

I've actually got quite a few pizza this way. If this NP solution helps to speed up pizza delivery, I don't I would like that, at all.

Re:I would really hate that!

[dpilot]

Have any of your pizza delivery boys ended up with their vehicles in a neighbor's swimming pool, and ended up giving your pizza to a skatboarding girl to make the final delivery?

Re:I would really hate that!

["Zow"]

An alternative method is to live close, but have an address that's just really hard to find: growing up I lived in a city that had a pretty consistant grid layout to the streets, at least in any part of the city that was more than 15 years old. We lived on this little street that curved right through a couple of these otherwise nice rectangular blocks. I think it was all the free pizzas we got that caused Domino's to change their 30-minutes or free policy - the complaints about reckless driving were just a red anchovie.

The name of the court I live on now is shared with the attached street, an avenue, and a boulivard (sp?) located in rather different parts of town. Since none of the pizza joints here have a 30-minutes or free policy, I just always pick up the pie because otherwise it takes about 2 hours and 3 phone calls for them to find us.

The moral to the story is that a linear (or even polynomial) solution to the TSP is not going to keep the pizza places from giving you free pies as long as you live somewhere that either causes the algorithm to bomb (like next to a circle that causes the program to get caught in an infinite loop), or at an ambiguous address.

-"Zow"

You're a little confused....

[11223]

For starters, what people are looking for is a O(n^k) solution, not a O(n), but one complication is that these problems may still take years to solve - your constant in front of n^k is just very very large. However, as time goes on (and Moore's law with it), they will get (comparatively) easier to solve, when compared to O(k^n) methods.

Secondly, there are very few encryption problems that are NP-complete. Now NP is a general class of problems that don't have a O(n^k) solution, but that's different than NP-complete. (I wouldn't want to use a NP-complete encryption anyway, given how much effort seems to be going into that area!) In fact, most encryption is based on the infeasibility of calculating discrete logs in Z mod n. However, this problem is very close to being solved itself. I haven't read up too much on what's going on there, but apparently they've been mapping Z/n to elliptic curves (don't ask me how).

Consequences of that? Well, for starters, if you can calculate a discrete log in Z/n, then it's relatively trivial to recover some multiple of the order of the order of the group - which makes primality testing easier (your order will be k*(n-1)). However, this means you should stick with elliptic curve-based encryption for now, as the NSA probably has discrete log cracked :-P

Re:You're a little confused....

[MasteroftheVoxel]

I think you are confused actually.

I can't comment on the math in the second half of your posting but your definition of NP-complete is wrong on many levels.

First of all, it isn't known whether NP is equal to P or not, so its nto safe to say that there is no O(n^k) solution to those problems. This is minor because it is widely believed that P!=NP.

Second, NP is a superset of P. That means all the problems in P are also in NP!

Third, your definition is wrong. NP is the group of problems that can be solved by a nondeterministic turing machine in polynomial time. If you don't know what this means, there are several good books out there. Come back to this post when you have read them.

Fourth, it hasn't been shown that there are ANY problems in NP, but not in P, but aren't NP-complete! That means all the so-called NP (excluding P here) problems we know of are NP-complete! Now they may be some that lie "between NP-complete and P but no one has found one yet. Or proven that a problem we know of lives in this set.

Lastly, there are harder problems than NP-complete problems. See PSPACE and EXPTIME.

Re:You're a little confused....

[crab]

>That means all the so-called NP (excluding P here) problems we know of are NP-complete!

That's not true. Factoring and discrete log are NP but not shown to be NP-complete. It is relatively easy to show that some problem is in NP (If you can check an answer for validity in polynomial time it is in NP). Much harder to show that it is NP-complete (Need to show that the SAT problem can be solved in poly time if the given problem can be solved in poly time).

On another note, quantum computers can solve factoring and discrete log in poly time thus breaking most cryptosystems. However, it is believed that quantum computers will not be able to solve NP-complete problems in polynomial time.

An interesting question is that if P!=NP then are there some problems that are not in P and not in NP-complete. The answer is not known but factoring could be a candidate.

sa?

[autopr0n]

Of course, here he can post stuff for free, and have it seen by a wider audience.

If I solved it...

[Baloo Ursidae]

...I'd break the news a lot like Linus did when he released 2.4.

"Oh, and by the way, here's the solution to some NP complete problem..."

NP is not O(n)

[nsample]

Okay, kay, I'll concede the possibility that P=NP, because I'm bored. And just maybe quantum computers will allow us to bend the Von Neumann/Turing rules that we've been saddled with these o'-so-many years...

To answer the question about crypto then, will it break? Yes, definitely, crypto as we know it will break. Public Key Crypto is effective because the time to generate a private key from and unknown bit of salt and a private key is NP. That's why people don't brute force PGP... the naive brute solution is exponential in n, where n is the length of the key (2^n, where |n| is in bits).

But here's the rub: If you reduce such a problem to linearity (O(n)), then the only protection you have is increasing the length of n. But, to encrypt a message is still in O(n)*.

• It would take only as long to crack a private key as it takes to encrypt a message.

So, protect yourself with larger values of n all you like, but it takes exactly as long to crack a message as it does to encrypt one.

* the oddity is that it takes more time than O(n) to encrypt a message. But, it is in P. and if P=NP, the all polynomial time algorithms are O(n). Kinda sounds silly at the end of the day...

Re:*sigh*

[fiftyfly]

"If only it was easy to find any decimal of PI with a simple formula, [blah blah]" There is - for hex - that's how they compute it these days.

Understand NP-completeness, please

[larse]

It would only mean that NP-complete problems would now have a polynomial solution. It would *not* contrain the exponent of the polynomial, so they could still (and likely would still) be very hard.

No

[autopr0n]

Most crypto algos are not NP complete. You can solve 'em it just takes a ton of time (but you can calculate how long it's going to take.) Doing NP complete problems in O(n) time won't help you break crypto at all.

Re:The Big if

[furiousgeorge]

"Fetmat's Big Hunch"?

Care to give a reference...... I did a google search on that and came up with nothing...

If you're thinking about 'Fermats Last Theorem', it was solved in 1993/94 by Andrew Wiles.

Oh no!

[autopr0n]

They can crack RSA crypto in O(n^123,312,352) The world is doomed!!!!

'polynomial time' can still be a long-ass time.

Re:Advance in computer science?

[Wavicle]

There is an NP Complete problem affecting the backbone of the internet:

Several router manufacturers are designing their new equipment with support for MPLS. MPLS, among other things, offers better support for traffic engineering. Traffic engineering means deciding which router hops to take to get from border point A to border point B (it also means you can select an alternate route depending on network congestion or backbone router failures).

Finding the most efficient path between the two endpoints is an NP complete problem.

I think this problem also exists for BGP/IGP networks, but I'm not experienced with them. I do know that the promise of the internet being secure and redundant and safe from one node being bombed is a bunch of nonsense. Although the technology to route around outages exists, the chore of houskeeping for it has turned out to be rather intractable so it is minimally implemented at best. Usually if a large backbone provider suffers a hardware failure and can't swap in a backup, they call in one of their router guru's to look at their topology map and configure their other routers to route data around the bad router at that time. That's the automated process.

All the providers out there would *REALLY* like a tool that could take their network topology map and output a reasonable set of LSPs (MPLS tags that indicate the route the packet is to take) for them in a reasonable amount of time. However, since this problem is NP complete, such a tool would have to compute every possible path and then choose those at the top of the list.

What?

[Tim C]

Sorry, that was a question?

If you could do that, publish it.

Stuff the collateral damage, that in itself would be a major achievement.

Sciene is not progressed by discovering things and keeping them to yourself...

Cheers,

Tim

Misconceptions

[s20451]

Firstly, an affirmative answer to the NP=P? conjecture only means that there is a solution to every NP-complete problem in P. That is, there exists a solution for every NP-complete problem that is O(n^d), where d is a constant integer. If d > 3, the solution would be practically infeasible anyway. Furthermore, even with an O(n) problem, this only means that the computational complexity approaches C*n in the limit of large n, where C is some constant. If C has to be arbitrarily large, or there exists a large constant additive factor in any potential solution, again the solution is infeasible.

Furthermore, the security of public key cryptography does not rely on NP!=P. It is not known whether the discrete-log and integer factoring problems are in NP (I think ... correct me if that's wrong). In fact, some CS researchers believe public key cryptography to be insecure, since some brilliant person could come up with a feasible factoring algorithm tomorrow, without requiring that NP=P.

Re:Misconceptions

[mj6798]

O(n^d), where d is a constant integer. If d > 3, the solution would be practically infeasible anyway.

As is common, you are overestimating the significance of worst-case complexity, and you are assuming that "n" can get arbitrarily large. In the real world, "n" is often bounded by constraints in the real-world, and algorithms have much better average case complexities than their worst case complexities. I routinely solve problems whose worst-case complexity is O(n^8).

Re:Misconceptions

[mj6798]

First of all, upper bounds like O(n^5) don't tell you at all whether a problem is hard or an algorithm is slow--it might still run in linear time in all cases. If you mean a worst case lower bound o(n^5), that still only tells you that some problem instances may be harder. But finding such problem instances may itself be hard, so it doesn't necessarily help you with cryptography. And worst-case lower bounds still tell you little about the existence of good practical algorithms, like randomized algorithms.

Worst case upper bounds are good only for one thing: to prove that a problem is easy. They are useless for proving that a problem is hard.

Re:Depends *which* NP-Complete problem gets solved

[Dominic_Mazzoni]

Actually, you can use a polynomial-time solution to ANY NP-complete problem to construct a polynomial-time solution to any other NP-complete problem. That's what NP-complete is.

Decryption not NP-Complete, Implications of Poly

[fireboy1919]

Not all encryption schemes are NP-Complete! Most are actually just NP-Hard because you can't tell whether or not you've found the correct decryption. So, decryption schemes will not be solved even if you can convert into NP complete problems into NP problems. It will be a lot easier though.

That polynomial can still be huge, say N^1000. Except for really large N, current exponential-time algorithms could be superior to polynomial-time ones.

This lacks some of the insight into NP and NPC problems. We only care about the large cases for the most part. On the small scale (small being relative to the problem), exponential solutions are always easy to solve.
There are some amazing implications of this anyway. For instance, we can solve chess (find the best possible game), and all other decidable search problems.

Keep in mind that our computer improvements allow us to make polynomial time reductions in the amount of time that the problem takes.

Re:*sigh*

[floW enoL]

>If someone could find a way to turn mercury into gold, [blah blah]

As any chemistry class can tell you, this is practically impossible.

>If a person could find an function f(x) that returns the xth prime number, [blah blah]

Actually, you can. Anyone proficient in a programming language can code one easily enough, and anyone with any math experience can write out a description of said function. I think you meant a "simple" function f(x) (i.e., non-recursive), which I think has been proven impossible (although don't take my word for it).

>If only it was easy to find any decimal of PI with a simple formula, [blah blah]

It is. See other replies to your post.

>"If a person were to find a O(n) solution to an NP complete problem [blah blah]"

What's so different about this question? It's still open! All the examples you posted are either solved or proven unsolvable. This question is neither.

More good things

[zunger]

The thing we would get if someone were to find a polynomial-time algorithm for any NP-complete problem is an immediate, poly-time algorithm for every NP-complete problem. This is because the definition of NP-complete is that there is a (known) poly-time algorithm to turn any one NP-complete algorithm into any other, so just by composing these two you get them all. (I'll attach a glossary at the bottom -- most people on this list probably aren't mathematicians :)

But OK, what does this mean realistically? The good news is that there are several very useful NP-complete problems; probably the best known (as someone has already mentioned) is the travelling salesman, and being able to do fast TS problems could mean incredible reductions in cost for shipping of goods and things like that. All sorts of problems in computer network architecture are also NP-complete; think about trying to design an internet which is both fault-tolerant and maximizing bandwidth.

The bad news: There are two things. First of all: This does not mean encryption of any sort is broken! The heart of public-key crypto is that factorization takes exponential time (or more specifically, the discrete logarithm, which is at the heart of fast factorization, takes exp time) and so if you could do poly-time factorization, you could break various algorithms like RSA. But factorization is only conjectured to be NP-complete; there is no proof, and in particular the explicit algorithm which would be needed to use a poly-time algorithm for some other NP-complete problem for factorization isn't known. This doesn't mean it can't be done; it just means that there's one other significant step between finding such an algorithm and breaking crypto.

The second problem is that even a poly-time algorithm isn't necessarily useful if the coefficients are large. What poly-time really means is that, in the limit of very large inputs, computation time doesn't go completely out of control; the fact that (to the best of current knowledge) factorization isn't poly is what makes adding one digit to key size enough to increase the difficulty of decryption by a factor of two. (i.e., the work increases as an exponential of the input) So this is important when you're trying to create "sufficiently large" inputs to jam up an algorithm. But for real-world problems that people are trying to solve apart from crypto, an O(N^1000) algorithm might technically be "better" than an O(e^N) algorithm but practically still be way out of reach.

In fact, most of the interesting NP-complete problems such as travelling salesman are routinely worked on by methods which give approximate answers in fairly short time; this turns out to be more than good enough for a remarkable range of uses, which means that the advance of getting poly time wouldn't be as earth-shaking for most real-world applications.

Even if P == NP, not out of the woods yet

[pclminion]

Even if P == NP, this just means that all NP problems can be solved in polynomial time. This does not necessarily mean linear time. An algorithm of order O(n^100000000000) is polynomial time, but it certainly isn't fast.

Even linear problems can take a long time to solve. Remember that algorithmic order represents asymptotic behavior -- how does the algorithm perform as the input size goes to infinity? A linear algorithm where each operation takes a trillion clock cycles will, in practice, be much slower than a quadratic algorithm where each operation takes only one hundred clock cycles; at least for "reasonable" input. In the real world, N does not go to infinity!

It's even less important than that.

[Nindalf]

In real-world situations, you don't have accurate data for the cost of each link. Only approximations, built on probabilities of delays, estimates of how many packages will be ordered, etc.

The miniscule gain of selecting the best possible path rather than just a very good path would likely be reduced to an imperceptible gain when applied to rough real-world estimates.

There would be some extremely important consequences of P=NP, but direct application of a faster optimal solution of the Travelling Salesman problem to real-world travelling is not likely to be one of them.

Re:what about normal 128 bit encription

[pthisis]

(Insert obligatory comment about factoring primes being trivial here)

Symmetric crypto is already considered to be stronger than the available public-key methods. Well, stronger may be the wrong word: better studied and less likely to fall to a sudden advance in mathematics.

Most systems that use public key crypto (including e.g. PGP, ssh, ssl, all of which use RSA most commonly) use the public key method only to exchange a key and then use that key with a symmetric algorithm (most widely 3DES (SSH), IDEA (PGP), and RC4 (SSL), but plenty of others are common)

This approach limits the amount of crypto text (and known plaintext) available to attack the PK system with.

Sumner

Factoring is NP hard

[Tom7]

I'm pretty sure factoring is in NP. (The solution will be polynomial in the size of the input, and verifiable in polynomial time.) If someone were to prove P=NP, we'd have "fast" solutions to all of the problems in NP, not just the NP complete ones. (That's never gonna happen though..!)

Re:Advance in computer science?

[SpinyNorman]

I've discovered a wonderful linear way to calculate optimal routing that I'd like to share, but unfortunately my keyboagu;[f=s af\sdfgsv asdfw352.,.f354asf

Re:*sigh*

[quokka70]

>If a person could find an function f(x) that returns the xth prime number, [blah blah]

Actually, you can. Anyone proficient in a programming language can code one easily enough, and anyone with any math experience can write out a description of said function. I think you meant a "simple" function f(x) (i.e., non-recursive), which I think has been proven impossible (although don't take my word for it).

There are simple functions f(x), for appropriate definitions of "simple". Here is one.

Define the constant A by:

A = \sum_1^\Infty (p_n / 10^(t_n))

where \sum denotes summation, p_n is the n-th prime, and t_n is the n-th triangular number. Then A = 0.2030050011... In particular, A is a constant, and so "simple". Now define the function

f(n) = floor(10^(T_n) * A)

where floor is the integer part truncation of the argument, and T_n is the sum of the first n triangular numbers:

T_n = 1 + 3 + 6 + ... + t_n

Then, up to bone-headed off-by-one type errors on my part, f(n) = p_n.

You may or may not regard this function as "simple". It is almost certainly not useful for generating primes.

It is not hard to show that no non-constant polynomial can take on only prime values as inputs range over the integers. Rather more interestingly, there are (multi-variate) polynomials whose positive values are exactly the primes, but who also take on a bunch of "junk" negative values.

Cheers, quokka.

The answer is clear....

[Mr. Neutron]

Prove that it's impossible to solve NP-Complete problems in linear time, before someone figures out how to do it.

Check your theory

[OeLeWaPpErKe]

EVERY np complete problem can be mapped on any other (because it can be expressed in a simple logic language, and given one of the solutions you can generate any other by doing math with the solution you have). If you can calculate something that takes infinite processing power, you can calculate any other thing that requires that same amount.

The implications would be simple yet brutal, breaking a key of 128 bits would require 128 times the amount of time to break a 1 bit key.

There are still stronger mathematical formulae, but they must have continuous key spaces for encryption to work, if they want to defeat this, in other words, you will not only need an infinite amount of possible keys, but also an infinite amount of keys between any two given keys.

But that's not more than normal ... you can destroy public key encryption in a simpler way ...

The security of PKE is that you cannot easily determine the exponent of a given number. In other words given a and (a^n mod m), you cannot easily determine n. Right now there are algorithms that only work if n complies with a simple restriction. The alternative to that method is trying everything out. If some smart mind can generalise those algorithms we would have lost encryption as we know it ...

I only know a dutch text discussing this ... "Fundamenten van de informatica" by B.Demoen

NP Complete is NP Complete

[redhog]

"It would be interesting to see how many problems we could map into the NP Complete model."

The point is, everything that is not NP-complete, and still computable that has been found by man to date, is NP-complete (that is, exponential; O(a^n) for some a). The definition of NP-completeness is that it, using an algorithm of polynomial complexity (or O(n^a) for some a), can be mapped onto any other NP-complete problem, and thus solved using algorithms for it.

Thus, if an algorithm where found to solve one specific NP-complete problem in polynomial time, all of the NP-complete problems would be possible to compute in polynomial time (polynomial time to map it onto that particular problem for which we have the algorithm, plus polynomial time to solve it, and a polynom plus another is still a polynom).

Trivia: The "standard" NP-complete problem is SAT, which is the problem of finding out if there exists assignements of truth-values (TRUE and FALSE) for the variables of a logic formula, that makes the value of the formula TRUE.

Re:Decryption not NP-Complete, Implications of Pol

[roystgnr]

This lacks some of the insight into NP and NPC problems. We only care about the large cases for the most part.

How large is large? 2^128 (for brute forcing common encryption) is pretty much impossibly large, but is 128^1000 (to use the original poster's example) really an improvement?

A slide from class

[JohnZed]

So, this question came up in an algorithms class at Princeton. To the best of my memory, the slide answering it said:

"What if P = NP?"

"BAD:
- Many computer scientists out of work

GOOD:
- Perfect societal bliss"

The point is essentially this: verifying the value of an answer to an optimization problem (of any kind) is usually easy. But finding a better solution is usually hard (exponential). So, saying "P=NP" is equivalent to saying "Finding an optimal answer is not really harder than verifying if an answer IS optimal." So, finding the optimal design for an aircraft, the optimal routing for a network packet, the optimal anything, is not really that tough. And that wouldn't be such a bad thing for our society (though "perfect bliss" was probably an exaggeration).

Re:Decryption not NP-Complete, Implications of Pol

[zmooc]

Large in this case usually means infinite:) It's all about how the function t(n) behaves where t is the time necessary to compute the value of a certain function f(n) relative to n; it's not about comparing 2^128 to 128^1000 but about comparing 2x to x^2 and 2^x to log(x). Read Herbert S. Wilf's Algorithms and Complexity if you want to know more about it. It's the book we use in school (and it's downloadable for free).

It'd be awesome!

[TheSHAD0W]

A boon to traveling salesmen everywhere!

:-)~

Re:Shor's Algorithm

[MasteroftheVoxel]

oh boy.

From the perspective of theorectical computer science this means nothing. NP problems are measured by the speed they run on DETERMINISTIC *turing machines* which means traditional computers and the like. Remember that NP problems can be solved by nondeterministic turing machines in polynomial time. No one cares how long it takes on a quantum computer, because they aren't deterministic turing machines.

And if one NP-complete problem were found to have a polynomial time solution on a deterministic turing machine we could reduce all the other NP-complete problems to this problem in polynomial time and solve them just as fast. This is how one goes about showing a problem is NP-complete

Like I said

[fireboy1919]

We can make polynomial improvements by getting better hardware for most problems. What we can't do is make exponential improvements. This is why it is trivial to solve most kinds of polynomial problems.

All NP-complete problems can be considered search problems. All search problems can be parallelized.

Re:Like I said

[fireboy1919]

I'm not sure you quite understand the difference enough to understand my comments. Let me formalize the definitions for you of NPC and NP-Hard. This is taken straight from my textbook (I'm a grad student at Purdue University).

The simplest, and main way that NP completness is proven is by showing

1) A decision problem may be transformed in polynomial time into another NP complete problem

2) The solution to the problem may be verified as correct or incorrect in polynomial time

If only condition 1 may be met, then the problem is considered NP-Hard. This is what I meant when I said, "merely NP-Hard" - they haven't the ability to go the full distance towards a proof of NPC.

The decision problem in this case is "Does this key decrypt this data?" The answer is undecidable. Hence, most decryption is NP Hard.

Now lets look at your case. Almost all problems can be trivally converted into decision problems (and back, but I'll leave the inverse conversion to you as exercise) in polynomial time, given the proper context, including the ones you presented. The decision in the first case is "Is there a clique of size k within Graph G?" while the second (transformed into a decision problem) is "Is the maximum clique of size K in Graph G?"

As you see from the criteria you have presented, both would be considered NPC. However, given my criteria, the first would be NPC if condition #2 is satisfied (it is), while the second would NP-hard, because you cannot prove in polynomial time that any solution is optimal.

Re:Like I said

[Furry Ice]

I'm sorry, but you've got your definition a bit screwed up. I'll clarify:

A problem B is NP-complete if it satifies two conditions:

1. B is in NP
   
2. Every A in NP is polynomial time reducible to B
   

An NP hard problem is one for which the second condition holds. The first does *not* need to hold. The difference between this and your definition is that the reduction goes in the other direction. You don't reduce the problem to NP-complete problems, but rather reduce NP-complete problems to the problem in question. There are NP-hard problems which are not in NP, and thus cannot be reduced to them in polynomial time.

Re:Like I said

[fireboy1919]

Learn to read. I've said it twice now. You even quoted me. I WAS REFERRING TO THE PROOF WHEN I SAID "MERELY NP-HARD." Does this make sense yet? Let me try again to be more clear. The proof for NP-Hardness is much easier than the proof for NPC because all you have to prove is a reduction to NPC, and not a polynomial verification of the solution. Hopefully you understand now.

Nowhere did I say that NP-Hard was easier to solve than NP. You inferred that this is what I was saying.

Why didn't I come right out and say that NP-Hard is at least as hard as NPC? Well, I would assume that if you were actually reading the constraints it would be obvious.

Re:Like I said

[fireboy1919]

You're right. I never remember which to convert to which.

Re:Advance in computer science?

[nobody/incognito]

Finding the most efficient path between the two endpoints is an NP complete problem.

huh? dijsktra's algorithm solves the shortest path problem in O(n^2) for the general case, O(n log n) for most real-world problems, in which the graph is sparse.

nobody

A more interesting question

[SIGFPE]

What would happen if *all* terminating algorithms could be made to run instantly?

I'm not sure it's obvious what the answer would be. For example - would we be able to cure cancer? You might just say "simulate the whole human body and simulate throwing a googleplex different drugs at it". But in order to do that you need to have an accurate physical model - accurate down to every molecule in a person. That's still hard.

So imagine an 'oracle' like this suddenly appeared somewhere. What impact would it have on society for the next few centuries?

(There's also the issue of what kind of interface this device would have. Lets say it has some kind of serial port that appears to be able to respond to signals sent into it no matter how fast they are).

A proof.

[Debillitatus]

Similarly, we know there are an infinite number of primes, just that nobody has been able to prove it.

Other posters have pointed out that this was proved clasically (and by classically I don't mean last century, I mean like 500BC or whenever Euclid was around), but not only is this a classically known fact, I will reproduce the simplest proof I know here:

We will prove this by contradiction. We will assume that there are a finite number of primes, i.e. that there is a largest prime. Let's number them p_1,...,p_n.

To show N is prime, it suffices to show that it cannot be divided by any smaller number (except for 1). Even better, it suffices to show that N cannot be divided by any smaller prime (since if a smaller number divided N, so would its prime factors). Consider the number

N = p_1p_2...p_n + 1

by which I mean that I multiply all of the primes together, and then add one. If I can show that this is not divisible by any of the primes, I am done. But consider what happens if I divide N by any p_k. Looking at the formula, p_k certainly divides the product evenly, so therefore if I divide N by p_k, I always get a remainder of 1.

Thus N is not divisible by any p_k. But thus it is not divisible by any smaller number, and therefore is prime. But since N > p_n, our "largest" prime, this is obviously a contradiction. Therefore there can be no largest prime, and thus there are infinitely many.

As I said, this proof is due to Euclid. There are many sources for this proof, and there are many other elegant proofs. There is a realtively advanced book called Proofs from the Book which gives elegant proofs to some well-known (and perhaps not so well-known) results. This is a nice little book, and, anyway, there are no fewer than six proofs that there are infinitely many primes. Not being a number theorist, I don't get all stiff about primes personally, but it's good stuff.

Somebody?

[talonyx]

Somebody want to explain to a non-mathematician (only in 1st year university, gentlemen) what P and NP are?
I'll give you a cookie if you do, and undoubtably you'll get a +5 Informative.

you too

[RelliK]

Now NP is a general class of problems that don't have a O(n^k) solution, but that's different than NP-complete.

false.

Definitions:

P is a class of problems that can be decided by a deterministic turing machine in polynomial time.
NP s a class of problems that can be decided by a non-deterministic turing machine in polynomial time. It means (literally) non-deterministic polynomial.

A problem is NP-Complete if:
1. It is in NP.
2. Any other problem in NP can be reduced (read: "converted") to it in polynomial time.

So, if a polynomial-time solution to an NP-complete problem is ever found, any other problem in NP will automatically have a polynomial-time solution. That includes most of the known algorighms.

Oh, and just to preempt stupid replies saying "it depends on which NP-complete problem is solved" or "perhaps the problem is misclassified": read the definition again. Any problem in NP can be reduced to an NP-complete problem in polynomial time; including another NP-complete problem.

Finally, a description of what P ?= NP question is:
P is a subset of NP (obviously). The question is whether it is a proper subset (i.e. P is strictly smaller than NP) or P and NP are actually coincident (i.e. P = NP). The answer so far is "probably not". There is a large number of NP-complete problems and so far no one has been able to come up with an efficient (i.e. poly-time) algorithm to solve any of them. However, P = NP implies that such algorithm exists (and vice versa).

(Stupid slashdot filter deletes less then signs)

Re:you too

[RelliK]

Last I heard, not all NP problems could be reduced to NP-complete.

You heard wrong. I suggest you take an algorithms course.

There are some (though not many I think) problems that are in NP but not NP-complete.

There are lots of problems that are in NP but not NP-complete. Most of the known algorithms are.

You're All Bloody Wrong

[tbo]

It doesn't surprise me any more when Slashdot displays large amounts of ignorance about non-computer topics, but I expected better for something like this. I've been skimming through the +2 and higher comments, and not a single poster has defined NP-complete correctly (this may have changed by the time you read this, but it was true when there were >50 comments at 2 or above).

Here's the correct definition of NP-complete:
To be in NP-complete, a problem must be in NP--that is, it must be a concrete decision problem, and have a polynomial-time verification algorithm (i.e., if somebody hands you a solution to the problem, you can verify that it's correct in polynomial time). Furthermore, there must be a polynomial-time mapping from every problem in NP (not just NP-complete) to your problem.

My source for this is Introduction to Algorithms, by Cormen, Leiserson, and Rivest (yes, that's THE Rivest of cryptography fame), which is part of the MIT Electrical Engineering and Computer Science Series.

Now, some people have been getting confused and saying that being in NP-complete only requires there to be a polynomial-time mapping from every problem in NP. This is an understandable mistake, since the way one usually proves a problem is in NP-complete is by finding a polynomial-time mapping from one NP-complete problem to the problem of interest (which must already have been shown to be in NP). However, since you already know that there are polynomial-time mappings from every problem in NP to the NP-complete problem, there is thus also a polynomial-time mapping from every problem in NP to your problem. The difference here is that efficiently solving an NP-complete problem means you can efficiently solve all NP problems, not just the other NP-complete ones.

The second big error--the one that boggles my mind--is that the poster seems to have confused O(n), which is linear time, with polynomial time. True, O(n) implies polynomial running time, but polynomial-time does not necessarily imply O(n)--you could have O(n^2), O(n^3)...

The third mistake is the implications of any polynomial-time solution to an NP-complete problem--even if it is O(n^1000). A few people here are claiming a polynomial-time solution would be irrelevant if the order of the polynomial was large (giving O(n^1000) as an example of large). For moderately large inputs (and we're really not talking that large), O(n^1000) is better than O(e^n). Taking the example of O(n^1000), n only has to be greater than 10,000 for O(n^1000) to beat O(e^n). Exponentials grow fast, people.

Finally, getting to implications, any polynomial-time solution to any NP-complete problem would instantly destroy public-key cryptography. Even if everybody immediately switched cryptosystems, the implications would be staggering, because someone could have archived all sorts of encrypted transactions, the contents of which are still sensitive. My understanding is that prime factorization is in NP, but not in NP-complete (not that this matters too much, as I explained earlier). Not sure about the math other forms of PK crypto are based on, but I suspect it's also NP.

On the plus side, protein folding simulation is suspected to be in NP (this may have been proven--not sure). If you could do protein folding simulations efficiently, it would make finding a cure to most diseases a hell of a lot easier (and we'd finally be able to figure out what the hell the human genome means).

Re:You're All Bloody Wrong

[jclip]

This is the only person thus far who knows what he/she is talking about. Everyone else should RTFFAQ and mod this up.

Re:You're All Bloody Wrong

[e_lehman]

A few people here are claiming a polynomial-time solution would be irrelevant if the order of the polynomial was large (giving O(n^1000) as an example of large). For moderately large inputs (and we're really not talking that large), O(n^1000) is better than O(e^n). Taking the example of O(n^1000), n only has to be greater than 10,000 for O(n^1000) to beat O(e^n). Exponentials grow fast, people.

But 10,000^1000 is a four thousand digit number! So this is not a meaningful demonstration of the superiority of polynomial time vs. exponential time. A running time of n^1000 is impractical even for n = 2-- that gives a three hundred digit number.

Re:*sigh*

[Debillitatus]

>If a person could find an function f(x) that returns the xth prime number, [blah blah]

Actually, you can. Anyone proficient in a programming language can code one easily enough, and anyone with any math experience can write out a description of said function. I think you meant a "simple" function f(x) (i.e., non-recursive), which I think has been proven impossible (although don't take my word for it).

Well, if you want to define function in any way you want, then of course, I can find a function which returns the primes. I define f so that f(n) is the nth prime. Woo.

Of course, this function is completely meaningless. The poster was of course saying that it would interesting to find a function which allowed you to compute the nth prime without knowing the primes already. This has not been found. Of course, you can't prove that it's not possible, because our conditions are pretty vague. I mean, there are certainly many smooth functions whose value at n is the nth prime. And for any finite number N, there is even a polynomial whose values at 1,2,...,N are the 1st, 2nd, ... , Nth prime. But unless you could say something about these functions, then they are useless.

For example, there is a function whose value at 0 is the time of my birth,at at 1 is the time of my death. Claiming there is such a function doesn't tell me much.

>If only it was easy to find any decimal of PI with a simple formula, [blah blah]

It is. See other replies to your post.

I was going to reply to this elsewhere, but since I'm already typing...There is a result where one can calculate the nth digit of \pi in hex (and I think in any base which is a power of 2), but, surprisingly, there is no analogous algorithm for base 10. So you might say, well, the hell with it. Just compute the nth digit in hex, and then convert. But, to convert from hex to decimal to find the nth digit, you would need all of the preceding digits. A funny little Catch-22. Although, it's certainly possible that there is an analogous base 10 algorithm, just noone knows it.

Clarification

[tbo]

Pardon me, the fourth paragraph should read:

Now, some people have been getting confused and saying that being in NP-complete only requires there to be a polynomial-time mapping from every problem in NP-complete, and that it does not imply a mapping from NP in general....

Re:Decryption not NP-Complete, Implications of Pol

[Daniel]

Large in this case usually means infinite:)

Yes, I'm sure the previous poster knew that.

The asymptotic performance of an algorithm is not everything; if you actually want to use it, constants matter too. (ask your algorithms teacher why everyone isn't using the linear-time mediant algorithm for their quicksorts, for instance)

The point the previous poster was making (which I will remain agnostic on) is that if someone manages (heh) to prove that P=NP, solving a given NP-complete problem might have such a large constant or (worse) exponent that for PRACTICAL PURPOSES it doesn't allow us to do anything new.

Daniel

Re:Not likely to find that P=NP

[mbrubeck]

You must have meant to write something else. Euclid has a simple proof that there are infinitely many primes.

The writer most likely was thinking of the famous open question, Are there an infinite number of twin primes? Twin primes are pairs of primes whose difference is 2, for example 17 & 19, or 41 & 43. It is conjectured but unproven that the twin primes are inexhaustible.

NP is Optimization

[chiguy]

P=NP only means NP-complete problems are solvable in polynomial time O(n^t) where t is some constant (possibly very large constant).

The simplest problem to understand in NP space is optimization. EVERY optimization problem is NP-complete. If you want to find the shortest route to visit every city in the US, this is an optimization problem.

What a problem being in NP-complete space means is that if you can solve one problem in the space, you can solve all problems in that space (by transforming the other problems to look like the solved problem and then solving that).

So if you prove P=NP, then you can solve optimization problems in polynomial time O(n^t). Pick a problem where you could say "I wonder what the fastest/shortest/lightest way of doing this is?" and you could solve it in O(n^t).

4 caveats/common misconceptions:

O(n^t) could be very VERY large. n^237203 still takes a very long time.

As far as I know, encryption algorithms are NOT KNOWN to be NP-complete. So it's UNKNOWN what proving P=NP means to the encryption world.

People who say P=NP is not provable aren't conveying the situation. The situation is that it is UNKNOWN if P=NP or not. They don't know the answer.

There are problems that do not fall into NP-complete class. There are NP problems that are not complete. There are (provably) problems that cannot be solved. So P=NP doesn't really act as a cycle multiplier (you don't just get more pure computation), it just gives you another trick in your bag.

So my answer for what happens if P=NP is proven: Everything in the world gets cheaper.

Re:NP is Optimization

[Anonymous Coward]

Ummm. maybe you have a peculiar definition of optimization, but some optimization problems are not NP-complete. For example:

shortest-path on a graph
matrix chain multiplication
polygon triangulation
Huffman encoding

I could go on, but I won't.

GS

Answering the actual question

[William Tanksley]

It's interesting how most of the answers here fail to look at the actual question. The question wasn't so much, "what will break;" the question was, "what should one do."

Although it's interesting and even essential to review what parts of computer science or our economy would be toppled by such a discovery, doing so doesn't answer the question.

Let me rephrase the question for any who missed it: "Suppose you discover that P=NP. What is the right thing to do?" Do I cover it up, or do I release? What if I proved that P=NP, but I don't know of an algorithm to actually convert any known problem? Or, what if I did know the algorithm and the proof, and I believed that the algorithm couldn't be reconstructed from the proof -- should I release the proof?

This is a powerful question!

My feeling is that the truth should be known, but experience shows that information without knowledge, and knowledge without understanding, can be deadly. (I'm afraid you can't affect whether people will get understanding without wisdom, so we'll stop the natural progression before we reach that point.) A little survey of the literature (please see the other posts here; they've got GREAT info) shows that the practical benefits of this discovery would be IMMENSE. The drawbacks seem huge, too; but if a particular algorithm has become easier to destroy, so also do new algorithms open up. Look around -- identify as many existing things which are harmed by your discovery, and try to provide a discussion of how to recover from the harm.

Even if you're not altruistic you want to do this; the person who is most essential in the new world isn't the person who discovered the info, since once the secret's out it's not under his control; it's the person on whom people are depending. Be that person -- but don't be selfish about it. Too selfish ruins the game too; there's always someone with enough power to take your position away from you.

So that's my knee-jerk answer, with a bit of reasoning: research the discovery, find who it hurts, and prepare to help them. Then make it public.

There's another question which is implied by the first one: to whom do I release info about my discovery? I can't answer that. Does anyone have an answer? I can say that you'll HAVE to release some information before you're ready to release it all; for example, you might want to found a corporation, and you'll almost certainly need library assistance. What can I say about that? Pick people you can trust, and don't trust them with too much.

-Billy

Re:Answering the actual question

[LazyDawg]

>Let me rephrase the question for any who missed it: "Suppose you discover
>that P=NP. What is the right thing to do?" Do I cover it up, or do I release?
>What if I proved that P=NP, but I don't know of an algorithm to actually
>convert any known problem? Or, what if I did know the algorithm and the
>proof, and I believed that the algorithm couldn't be reconstructed from the
>proof -- should I release the proof?

The question of whether or not such a world-altering technology would "make it into the wrong hands" is easy to avoid if you get this world-altering technology into *everyone's* hands, all at once.

For example, if you showed someone 50 years ago a PC from nowadays, they'd be like "Oh my god I could take over the world with this thing!" and possibly make a huge fortune. If, however, you gave one computer to every one of the billion people living back then, and showed them exactly how to manufacture more, they'd be like, "Oh, a new, faster, cheaper computer. So what?"

So, if you ever find that P=NP, spam EVERYONE with the solution. That way the "wrong hands" and the "right hands" think its a pretty commonplace thing.

Re:Answering the actual question

[William Tanksley]

When you say "all Turing machines" I assume you mean "all algorithms", of course.

Yes, that's the canonical P=NP solution. It's also completely useless (it may not even be implementable), thus bringing us back to my original point.

-Billy

Re:Answering the actual question

[William Tanksley]

I'm puzzled by your answer, since it seems you do follow my logic quite well -- you state very clearly that "it's unlikely that we'd be able to find efficient algorithms ... even if P=NP were known."

So go back to my post and read it that way:

1. I know an efficient algorithm, thereby proving P=NP.
2. I know a proof but no algorithm.
3. I know both a proof and an algorithm, and the algorithm can't plausibly be derived from the proof (I probably used the algorithm to derive the proof).

What do you do?

-Billy

Re:Answering the actual question

[plaa]

Let me rephrase the question for any who missed it: "Suppose you discover that P=NP. What is the right thing to do?" Do I cover it up, or do I release? What if I proved that P=NP, but I don't know of an algorithm to actually convert any known problem? Or, what if I did know the algorithm and the proof, and I believed that the algorithm couldn't be reconstructed from the proof -- should I release the proof?

This is definately a problematic question, one which I have also pondered often. As one reply says "spam everybody with it". Would this be a good solution? If you have an algorithm for it, or if one can be easily made from the proof, it would ruin most Internet security overnight. Would you want to cause certain chaos on the 'net, not to mention the financial consequenses (think every single bank's net-service vulnerable...)?

On the other hand, I don't think it would be right to keep it secret, because of the scientific value and because sooner or later it would be discovered.

But how can you prepare the world for such a blow? Obviously you would need to tell some people about it so preparations could be made. But to whom?

You could, of course, publicly announce that "I can prove that P=NP" and give a demonstration to some reputable people that you can solve difficult problems in reasonable time (assuming you have a working implementation). How long do you think it would take before the NSA is knocking at your door with shotguns?

Re:How to break encryption

[Debillitatus]

I think you've actually made the problem worse. I don't know what the complexity of GCD is, but you're giving it a factorial input, which is significantly worse that exponential, because n! is asymptotically the same as n^n, which is even worse than e^n. And GCD will be at least linear in the size of its argument.

On the other hand, you've not really done anything there. All you're roughly saying is, find the greatest common divisor of r and all numbers less than r, which is intuitively even worse than just factoring the damn thing.

Most block ciphers are no harder than NP-complete

[nickovs]

NP problems are, loosely, problems for which you can check that the solution you have is correct in a time that is a polynomial function of the size of the problem. NP-Complete problems are problems that can be converted, in polynomial time, to the boolean satisfiability problem, and the answer to the resulting problem can be converted back in polynomial time.

Given a plaintext/ciphertext pair most block ciphers can be written as boolean equations that are satified by the correct key (you may need more than one pair to be sure that there is only one answer). Thus, if NPC=P then most block ciphers can be broken in a time that is polynomial in the key length.

Of course the order of the polynoial may be so high that you don't care that much, and indeed is the order is greater than the key length then it's no better than exponential time :-)

Sci-Fi

[the eric conspiracy]

Interestingly this was the premise of a story published in Analog Science Fiction earlier this year. The end result in the story was a not so nice form of AI made possible by the use of more efficient algorithms. Parts of the story also referred to some of the poster's concepts of failed cryptography, etc.

I wonder if the poster was 'inspired' by this story?

NP Hard=/= NP Complete

[matrix0040]

NP hard problems will not be affected. The TSP and all the optimization problems are NP hard. NP complete means the solution can be checked in polynomial time, which is not true for optimization problems. Also factroring primes is not NP complete as there is no polynomial time algorithm yet to check if a number is prime.

Re:NP Hard=/= NP Complete

[jareds]

NP hard problems will not be affected. The TSP and all the optimization problems are NP hard. NP complete means the solution can be checked in polynomial time, which is not true for optimization problems.

You're simply wrong.

First, all NP-complete problems are NP-hard by definition. A problem is NP-hard if every problem in NP is reducible to it in polynomial time. A problem is NP-complete if it is NP-hard and it is in NP.

Second, TSP is a classic NP-complete problem. Formally, the problem is: given a weighted graph and a cost k, is there a Hamiltonian path with cost at most k? To verify the solution, you just take the path as the certificate, and verification is trivial: add up the cost of the path, check that it's not more than k, and check that the path is Hamiltonian.

Also factroring primes is not NP complete as there is no polynomial time algorithm yet to check if a number is prime.

(Insert obligatory comment about factoring primes here.)

Usually, the goal isn't to find the prime factorization of the input, but to find any factors at all. This is certainly true in cryptography, for example. In this case, verification is just multiplication, which is of course polynomial.

Flip of a coin

[GrEp]

I was at an interesting seminar today where one of my professors was talking about how P=NP seems to pop up in a lot of areas. The most intersting thing is that we can solve many NP problems in almost guarenteed polynomial time by using random techniques. As pseudorandom generators evolve we are able to generate numbers almost totaly random to the computation at hand.

The question may not be does P=NP, but are problems solvable in polynomal time in the same class as problems that can be solved using random methods, a class called BPP(Bounded-error Probabilistic Polynomial).

Re:Advance in computer science?

[Wavicle]

Good call. Clearly I need to pay better attention. The specific application was a QoS NMS.

So here's a link describing the NP complete problem (I think, I probably should read the whole thing first).

You are right, Dijsktra's algorithm will solve the general case shortest path from any source to every other reachable point.

Re:Decryption not NP-Complete, Implications of Pol

[roystgnr]

Large in this case usually means infinite

It's always easy to tell who's getting their CS degree and heading off to the workforce... and who's headed off to never-never land for their Ph.D. Large in this case usually means 128 bits. Really. I know about asymptotic analysis; I'm talking about actual programs.

Don't take that personally, BTW... I'm currently in CAM never-never land, and I'm just pissy that the spiffy O(n lg n) Delaunay triangulation algorithm I invented this semester doesn't seem to beat the standard O(n^(5/4)) algorithm for any problem size small enough to test on the 256MB RAM in my PC.

Simple Algebra

[servoled]

I think I have this P=NP problem worked out. All you have to do is divide everything through by P. That way N = 1. Now where is my prize?

Re:Advance in computer science?

[vrmlknight]

I dunno could be an interesting DoS attack :)

Just a few facts

[Lictor]

I have to say its wonderful to see TCS making an appearance on the front page of /. ... warms my heart.

Anyway, after perusing the comments (most of them quite good), I thought I'd point out a couple of common misconceptions in previous posts:

NP != EXP. Yes, for problems in NP the best *known* algorithms require exponential time, but no one has proven this to always be the case. Maybe we're just bad at finding algorithms (not likely though). All we can say for sure is that problems in NP require polynomial time on a non-deterministic machine. Non-determinism being the key problem here (and what forces these algorithms into exponential time when you run them on deterministic machines).

NP != BQP. E.g. you can't solve NP-complete problems in polynomial time on a quantum computer. There are two types of quantum algorithms out there at the moment, Shor-flavour and Grover-flavour. Shor-flavour algorithms can solve some specific problems (notably factoring and discrete log) that are in the intersection of NP and co-NP but are *not* NP-complete. Grover-flavour algorithms can solve database searching problems in O(sqrt(n)) time, despite the classical firm lower bound being O(n).

Its most likely that BQP and NP are disjoint so attempting to compare them may be a rather fruitless effort.

If the hardness of NP-complete problems really causes you to lose sleep, look into the field of approximation algorithms. In many cases we can get a very good solution, just not the optimal one. We can even given an upper-bound on exactly how 'bad' the solution we find is compared to the optimal one.

Just my two cents worth.

L.

Mixed up...

[Tom7]

Well, everybody seems to have their own ideas about what the various classes mean. Your post contradicts what I thought, so I looked it up:

NP-Hard: From a solution to an NP-hard problem, we can solve any problem in NP.
NP: Can check a polynomial-size solution in polynomial time.
NP-Complete: Intersection of NP and NP-Hard.

Thus, NP-hard problems are "harder" than NP-complete in the sense that a solution to an NP-hard problem gives you a solution to any problem in NP-complete.

I am almost positive that factoring is in NP, since it should be straightforward to check a solution in polynomial time.

http://www.cs.unb.ca/~alopez-o/comp-faq/faq.html

Solution to my problem

[Deflatamouse!]

Can anyone suggest a solution to this:

I have a lot of warez on my computer and running out of disk space. I need to burn those warez to 650mb CDs. But I want to use the space on those CDs efficiently, since I am too cheap to waste space like that :) Which means I need to find a way to burn X bytes of warez onto N cds. where (N-1)*650MB = X = N*650MB, N a integer, and X is closer to N*650MB than (N-1)*650MB. Would this turn into an NP complete problem?

karma whoring:

[wroot]

The question is thoroughly discussed and answered in a popular 90-minute RealPlayer lecture here

Wroot

Re:Decryption not NP-Complete, Implications of Pol

[MarkusQ]

There are about 10^120 positions in chess, if I remember correctly. Even if you could solve it, there'd be no possible way to store the answer

Not quite true; it is likely that the solution could be expressed as an algorithm that would take up much less space than an exhaustive list of state transitions.

For example, if you had a game where the goal was to take turns naming positive integers until someone was forced to name an integer larger than the one their opponent just named (and thus lost), there are an infinite number of states, but the "solution" can be expressed quite simply:

Say "one."

So, at least in this case, the solution is much smaller than the list of all posible cases. I suspect the solution to chess, while much larger than this, is still smaller that you propose.

-- MarkusQ

Take it from a graduate student.

[Chai_Bot]

Most people have incorrect misconceptions about NP/NP-completeness since this often isn't covered in many CS degree programs. Let me clear up a few things people seem to consistently post incorrectly about.

First of all, what is meant (most likely) is that some NP-complete language can be recognized in polynomial time. The complete in NP-complete means that EVERY language in NP can be reduced (in polynomial time) to this particular NP-complete language. So P=NP.

NP is the class of guess and check languages. For example, we can see that determining if a number is composite is 'in NP' by guessing a factor. We can check by seeing if our guess divides the original number. If the total time for the guessing and doing the check is polynomial in the input length, then the language is NP.

P is a subset of NP. So when you say a particular problem is 'in NP,' this doesn't necessarily equate with an (even potentially) intractable solution.

There are only a few problems which are in NP that are not either known to be NP-complete or known to be in P. One of these is factoring of integers and forms the basis for RSA. Another is the Discrete Log which forms the basis for Elliptic Curve cryptosystems. Both would be essentially broken if P=NP, but so would most other things.

One of the biggest consequences of P=NP is that P=PSPACE. This means that many problems thought 'harder' than NP are also solvable in polynomial time. For example, the level of 'GO'-playing computers would increase. Just about every computational problem imaginable is within PSPACE, so if you are wondering would 'xxx' be affected, the answer is probably yes.

It is believed that recognizing whether a number is prime or composite is already solvable in polynomial time (in the input length) (ERH). However it isn't certain if ERH is true, so recognizing if a number is prime is technically NOT (necessarily) in P.
In practice, it is possible to make the decision with arbitrarily high probability. The fact that it is still sometimes difficult to factor is what makes the problem useful for cryptography.

I hope this clears things up some. Maybe people will stop wishing for O(n) solutions for NP-complete problems...

Doh, what's the problem?

[TheLink]

Why should that be a problem? If it really were the answer to so many real world problems then just use your new found solution to figure out whether to make it public (and how) ;).

If it doesn't work that way, then why worry: just publish it I'd say. Get your Nobel Prize, have fun, be good.

Finding answers to questions is easy compared to finding the right question in the first place.

Also with humans sometimes just talking is good enough.

"What's the problem?"
"Dunno, nothing"
blahblahblahblah about nothing much in particular, esp things both already know about, for 20 minutes.
"Hey thanks!"

Funny eh?

Cheerio,
Link.

The difference between theory and real life is in theory there's no difference.

Re:Proof would probably mean...

[tbo]

No, a proof would not imply that the original classification as NP-complete was wrong (I assume you mean a proof that NP = P, which would likely take the form of finding a polynomial-time algorithm for an NP-complete problem). Re-read my definition of NP and NP-complete, and you'll see that nowhere do I state that an NP problem must not have a polynomial-time solution. The only additional requirement on NP-complete (as compared with NP) is that there exist a polynomial-time mapping from every problem in NP to that problem. Nothing requires that NP or NP-complete problems be "hard".

There's also no requirement that they be "easy", and, since nobody has found an "easy" NP-complete problem, we suppose (without any strong theoretical reason to do so) that NP != P. Now, we already know that P is contained in NP. If somebody were to find an "easy" solution to an NP-complete problem, it would mean that NP=P. NP-complete would still be a valid classification, although it wouldn't be nearly as interesting anymore (who cares if a problem is NP-complete if NP=P?).

In short, proving that NP=P wouldn't mean anybody screwed up (except all those suckers who trusted their secrets to crypto based on an unproven hypothesis).

The question itself, which was poorly phrased by the poster, is definitely very interesting, and is actually closely related to the subject of a talk I plan to give next year at the Canadian Undergraduate Physics Conference in Halifax.

Did anyone out there pass complexity theory?

[Blue Neon Head]

Because if you did, they should've known that prime factorization is not considered an NP-hard problem, but is more likely in neither P nor the hard subset of NP.

(Incidentally, it has been proved that either P=NP, or there exist problems that are neither in P nor NP-hard, of which prime-fac is believed to be one.)

Re:Decryption not NP-Complete, Implications of Pol

[fireboy1919]

That's exactly what I'm saying - we could find the absolute best.
By "solve" I meant, given that two computerized players both played a perfect game, who would win, the first player, the second player, or would it be a draw? This is the kind of question we could answer.

It seems impossible, but if you study AI a bit, you'll see that this is what NP=P implies, despite the seemingly enormous search space required by BFS, since chess is NPC. Obviously the solution wouldn't be using the BFS.

Re:Not likely to find that P=NP

[Blue Neon Head]

Guess it's time to find that one-way function whose inverse is EXPSPACE-complete!

Or better yet, undecidable altogether. Good luck on that one.

SNEAKERS! The guy died!

[statusbar]

Come up with a proof and tell people about it. Even if it only helps optimize the factoring of large numbers by 10%, no one will understand that it doesn't change the security of encryption much and Mossad, Saddam, the CIA, and the NSA will be after you. And you'll be dead just like the nice mathematician was in the movie Sneakers.
</conspiracy theory>

--jeff (off to watch more movies)

Re:The Big if

[joto]

Sure we do! It is partly proven by lost reference, secondly by authority (as Fermat was a pretty famous mathematician)...

This page will give you a clue...

As you will remember, Fermat claimed in the margin of some notes that he had a wonderful proof, but unfortunately it wouldn't fit there.

By the time this was written, it would count as proof by intuition and proof by obviousness, but this view has shifted through the times, and today the lost-reference and authority proof-techniques are viewed as the most strikingly elegant touches in this proof.

worst case is usually not relevant

[mj6798]

We only care about the large cases for the most part.

That's wrong on several counts. First, the worst case performance of an algorithm may not matter at all because the worst case is rare or because good randomized versions are available. Second, the constants on the asymptotically more efficient algorithm may be so much worse that it doesn't matter for problem sizes that occur in practice. You see, "N" isn't usually some kind of bragging factor, it corresponds to real-world entities, like people, components, cars, etc., of which there is a bounded number.

While occasionally theoretically interesting, many recently developed algorithms for solving common problems with slightly better asymptotic worst-case complexity are completely useless in practice.

Re:worst case is usually not relevant

[fireboy1919]

The cases to which you are referring are already solvable in practice so are not a concern for this discussion. What is of interest here is problems that couldn't be solved previously, such as, for instance, optimization problems. To find the optimal solution to most problems, even a normal case often involves a significant amount of search.

Everyones a critic.

Re:worst case is usually not relevant

[mj6798]

Far from it. You yourself gave an example: chess. P=NP is irrelevant to chess. Chess is played on an 8x8 board with 32 pieces. The problem isn't going to get any bigger. If P=NP, that doesn't mean that it would result in an algorithm that is of any interest to chess because current exponential time methods may still be faster in practice. And even if P!=NP, there can still be algorithms that solve chess games fast.

Even for optimization problems that (unlike chess) can scale arbitrarily, P!=NP doesn't mean that there are no good algorithms to solve them fast in any interesting practical sense. Only a positive result, P=NP, would establish that there are algorithms that scale "well" (in the sense of "polynomially") in all cases.

asymptotic worst-case complexity tells you little

[mj6798]

If you can get a good asymptotic bound for an algorithm, that tells you something useful: the algorithm will have a good asymptotic complexity also for the problems you encounter in practice. A bad asymptotic worst-case upper bound tells you almost nothing: the algorithm may still run fast on almost all cases, or it may run fast on those cases you encounter in practice. Not even a bad asymptotic worst-case lower bound tells you much, for the same reason.

Furthermore, for real problems, "N" often corresponds to real-world objects and doesn't get arbitrarily large, so the relevance of asymptotic results breaks down at some point: algorithms with worse asymptotic complexity may perform better in practice on all problems you would be interested in. This is probably rather the norm than the exception, although people often don't realize it.

So, if P=NP, that would tell you that a large number of problems don't necessarily require exponential time to solve in the worst case. But that doesn't make such problems easy. Conversely, many problems that are NP-hard have, in fact, good, practical solutions in many cases no matter whether P=NP or not (as some cryptographers had to discover to their dismay).

The real story of P and NP

[po8]

A problem is NP-complete if it is NP-hard and in NP. A problem is in NP if a guess of the answer can be checked in polynomial time. A problem is NP-hard if being able to solve it in polytime means being able to solve any problem in NP in polytime. To prove P=NP, it is sufficient to find a polytime algorithm for an NP-hard problem. (I believe I have seen a result that suggests that there cannot be a non-constructive proof that P=NP, but I can't offer a reference offhand.)

As other posters have pointed out, "in polytime" is not a panacea: the polynomial might be unbelievably bad, the memory requirements of the algorithm might be unreasonably large, etc. (But n^3 is way better than 2^n even for large n: do the math.) There is a belief in the business known as the Polynomial Thesis which suggests that anytime there's a polynomial algorithm, there's a low-order polynomial algorithm.

All the encryption schemes you have ever heard of are in NP: if you can guess the key, you can quickly check that it works. This is true for both private key schemes (trivially) and public key schemes (guess the factorization of the product of two large primes, and you can certainly check it quickly by multiplication). The crypto arms race would then turn to algorithms that use the power of the NP-solver to encrypt: there are results that suggest that this is possible.

Most practical problems which are compute-bound are in NP, and thus tractable for an NP-solver. This includes such things as production scheduling and many kinds of gene and protein sequencing and folding. A few practical problems are believed or known not to be in NP, such as general-purpose planning (PSPACE complete) and checking computer programs for infinite loops (semi-decidable).

Hope this helps. For more information, check out the classic book by Garey and Johnson.

Re:Advance in computer science?

[Lozzer]

I could be totally busking here, but just because a problem is NP complete doesn't mean you can't find a pretty good solution in polynomial time. I believe there is a genetic style algorithm (involving ants walking around a map where the towns supply sugar) that gives pretty good solutions to the travelling salesman problem in polynomial time.

No no no... you missed something critical

[Kjella]

Thus N is not divisible by any p_k. But thus it is not divisible by any smaller number, and therefore is prime.

No, this does not gurantee that N is prime, in fact for a simple example to the contrary: 2*3*5*7*11*13 + 1 = 30031 = 59*509. What the proof concludes is that N is prime *or* has prime factors not in the set of known primes. So the proof only establishes that there *are* more primes, but it does not provide any reasonable way to calculate primes.

By the way, nothing prevents a proof that NP-Complete can be solved in polyminial time, but doesn't provide any way of doing so.

Kjella

I solved it

[circletimessquare]

I solved it! I solved it!

I have the proof right here! I'm going to post it right now, right here on Slashdot!

Oh wait, there's a knock at my door. Hang in there folks, I'll be right back...

Muffled Yell

Thud

Long Silence

Re:I solved it

[uigrad_2000]

I did solve it.

The only reason I haven't posted it is because I can't seem to get it past the lameness filters!

Isn't it ironic?

Re:Decryption not NP-Complete, Implications of Pol

[fireboy1919]

You know what? You're right. It is PSPACE. I'm totally wrong. Thanks for the correction.

Crypto with prime products is insecure but ...

[crovira]

if someone uses private non-algoritmically generated keys to encrypt and decrypt, then the communications are probably secure.

If they use synchronized one-time pads then the communications are probably even more secure.

Don't get your hopes up ...

[Jobe_br]

NP completeness is something that you will come across in many undergraduate CS programs (e.g. Rose-Hulman Institute of Technology, my alma mater) and something you should most definitely come across in any self-respecting masters program for CS.

Once you start to understand NP completeness, you won't write statements such as:

... So if (when) the time comes ...

Many NP complete and NP hard problems have approximations that are extremely close to the optimal answer. A solution to an NP complete problem is unlikely. Quantum computing may in fact be able to solve an NP complete problem because it entirely changes the playing field for mathematical calculations - but who knows? We don't have any quantum computers yet that are more than a meager 'proof-of-concept'. Additionally, it has already been discussed that quantum computing would severely impact the longevity of cryptographic algorithms. I imagine researchers are working on quantum-safe cryptographic algorithms as I write this, though I don't know of any off-hand.

In short, NP complete is a difficult concept to even grasp the basic gist of, much less to fully understand and appreciate the magnitude of its implications. If you want to check out something I wrote on the topic for a master's class at DePaul, go here: http://www.webprojkt.com/brice/csc491/

Traveling salesman problem

[e_lehman]

Many people have pointed out that the Traveling Salesman Problem is NP complete, and so showing P = NP could have practical implications for the business world.

What this misses is the idea of approximation algorithms, which has emerged in recent years. The idea is simple: even though finding the optimal solution to a problem is NP-hard, finding a nearly-optimal solution may be easy. For example, finding the shortest path for the salesman might be very difficult, but finding nearly the shortest path isn't.

For the traveling salesman problem in particular, there is a polynomial time approximation scheme. This means that if you want a solution that is within 10% of optimal, you can get it in polynomial time. If you want one within 1% of optimal, you can also get it in polynomial time. In fact, you can approximate the solution as well as you want in polynomial time. The catch is that the degree of the polynomial increases as you demand better approximations. So, as a practical matter, the Traveling Salesman Problem is already solved. (At least for Euclidean spaces.)

Re:Actually N is not alway prime.

[Debillitatus]

No, read my proof more carefully. In the proof, we assume that there is no prime larger than p_n. Your example of 30031 is of course not prime, but under the assumption that the only primes are {2,3,5,7,11,13}, it is. This is because although it is divisible by a smaller number (59 and 509), these numbers cannot be prime by assumption, thus they each must have been divisible by a smaller number.

As you've pointed out, in either case you get a contradiction, and therefore the statement is true.

Unseen issues: I'm putting everyone on notice...

[freeBill]

...that I've stumbled across a NP-complete problem the solution to which will allow me to rule the known universe.

I'm not revealing it here, of course, because I don't trust everyone who reads this. (And I have very little desire to be ruled by someone else, especially if they stole the idea from me.)

I doubt this is the only such problem, so everyone should be very careful about publishing any solution.

Solved!

[mikeage]

I have this proved, I just don't have enough room here to write it out...

Approximation is usually good enough

[epepke]

The usual workaround is approximation.

Right, and approximation is almost always good enough.

Consider the kind of optimizations that are usually tackled by the simplex method, such as how much of each size shoe or model of computer to make so that you optimize your profits. The simplex method, worst case, is NP. Back in the 1980's, someone in the Soviet Union came up with a guaranteed P solution to those problems which I only vaguely remember (it involved ellipsoids, but that's all I can recall). Did everyone immediately switch? No, because

• Cases that aren't P for the simplex method don't seem to come up in the real world anyway.
• The simplex method is much easier to write and test
• The inputs to the simplex method are usually just guesses anyway, and you can get rid of the excruciatingly rare NP cases by perturbing the inputs
• If it's a little off, and you wind up with two pairs of size 12 shoes out of a thousand, who really cares?
• The stupidity of the CEO is more of a factor in making profit anyway

So, basically, the simplex method is plenty good enough, so people use it. The same is true of others. There are node-visiting problems that are NP, but you can get very close to optimal with simuated annealing or genetic algorithms, which are simple and converge quickly. Is it really worth saving a teacup of fuel by finding an exact solution, which will be way less than how much variation you get from delays on the taxiway?

It is really nice to have an exact, provable solution to a problem from an aesthetic standpoint. However, a solution that works in practice is usually all that is necessary.

As others have pointed out, factoring large numbers isn't even NP in the first place; it's just way harder than constructing two large primes. Even that is due to an approximation, an algorithm that tells you if a number is probably prime.

So, what would happen? We hard-core CS types would be ecstatic, but the rest of the world would mostly just shrug.