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. Well duh... by kilgore_47 · · Score: 1, Offtopic

    If we knew the answer to that, we'd already have the solution!

    And shouldn't this be under Ask Slashdot?

    --
    ___
    The way to see by faith is to shut the eye of reason. --Ben Franklin
  2. If I had that O(n) algorithm... by mfarah · · Score: 3, Offtopic

    I'd release it to the public, then sit down until they hand me my well-deserved Turing award.

    Seriously, there are more advantages (quick solutions to complex problems, like the traveller salesman) than disadvantages (cracking easily certain encryption mechanisms) to this.

    But then again, my gut feeling is that P!=NP.

    --
    "Trust me - I know what I'm doing."
    - Sledge Hammer
  3. Re:Crypto is safe by Nater · · Score: 1, Offtopic

    I really don't know why I spent so much time responding to an obvious troll, but it seems the moderators don't agree with me.

    Because you want so badly for them to agree with you. Guess what. They're gone now. This article is dead and the moderators have moved on to today's killings.

    --

    I like to play children's songs in minor keys.
    "We're all sons of bitches now." --J. Robert Oppenheimer