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
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.
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.
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).
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!