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