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.

3 of 525 comments (clear)

  1. Solution made public? by Soong · · Score: 1, Redundant

    The solution will never be made public. It will be abducted and dissapeared away into the NSA or worse.

    --
    Start Running Better Polls
  2. Re:Depends *which* NP-Complete problem gets solved by Dominic_Mazzoni · · Score: 2, Redundant

    Actually, you can use a polynomial-time solution to ANY NP-complete problem to construct a polynomial-time solution to any other NP-complete problem. That's what NP-complete is.

  3. Re:Crypto is safe by RelliK · · Score: 2, Redundant
    Factoring primes is not a difficult problem... the fastest known solution is already O(n)

    Oh, it's certainly not difficult. I can factor primes in O(1) time. Give me any prime and I'll tell you all its factors. However, the only known algorigthm to factor non-primes runs in exponential time. You got to love it when a clueless post gets marked "insightful" by even more clueless moderators.

    --
    ___
    If you think big enough, you'll never have to do it.