Slashdot Mirror
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.
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.
I like to play children's songs in minor keys.
"We're all sons of bitches now." --J. Robert Oppenheimer
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
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.
Erlang Developer and podcaster
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
Not publish your solution, go to the people in the know and use the knowledge to your advantage. Secretly rip of banks all over the world, bring down governments, get yourself in a position of power. The possibilities are endless.
There is also a chance that an agency such as the NSA or the British intelligence services have ALREADY found a solution. Just look at rsa, or how long the Brits kept enigma and their digital computers secret (predating ENIAC). Without a credible alternative to RSA at the moment it would be sensible for such an organisation to keep a solution secret.
Or have I just been watching too many spy films?
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)*.
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...
"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.
"Sanity is not statistical", George Orwell, "1984"
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.
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.)
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.
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.
Education is a better safeguard of liberty than a standing army.
Edward Everett (1794 - 1865)
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.
Toronto-area transit rider? Rate your ride.
>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.
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 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!
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
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.
Come on, give it up, that's
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).
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
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.
passetspike!
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. The original poster is indeed referring to the former context, while you seem to be referring to the latter.
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
If intelligent life is too complex to evolve on its own, who designed God?
Two points.
1: n/2 is still linear. You probably mean log N (what you get when you can halve your data set each iteration).
2: General comparison-based sorting is Omega(N log N). With more constraints you can get down to linear (radix, bucket sort). But for linear random lists you can't go below linear (you have to at least examine all the elements!
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
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:
l
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.htm
Wroot
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...
A problem B is NP-complete if it satifies two conditions:
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.
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.