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.
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.
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)
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
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)
___
If you think big enough, you'll never have to do it.
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!
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