Slashdot Mirror

← Back to Stories (view on slashdot.org)

Consequences of a Solution to NP Complete Problems?

Posted by Cliff on from the if-it-were-to-occur dept.

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.

2 of 525 comments (clear)

  1. RSA and all would *not* die by JF · · Score: 4, Interesting

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

  2. Re:Only the PK crypto by Dr.+Blue · · Score: 4, Interesting

    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!