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.

5 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:Sex Kitten! by rebug · · Score: 0, Offtopic

    i thought the point was another goatse link

    since both the beatles and stern are total shite, the hendrix comparison seemed out of place

    --

    there's more than one way to do me.
  4. Traveling Salesman Solution! by 3seas · · Score: 0, Offtopic

    If in Atlanta during rush hour on a bad traffic day.....

    The Answer is to get out of the car and start walking, unless you are lucky enough to have one of them Segways. Then you can fall you way there, and there and there.

    That compaired to having stayed in your car.... You did better then NP complete.

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