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. *sigh* by Rosco+P.+Coltrane · · Score: 1, Troll
    "If a person were to find a O(n) solution to an NP complete problem [blah blah]"

    If someone could find a way to turn mercury into gold, [blah blah]

    If a person could find an function f(x) that returns the xth prime number, [blah blah]

    If only it was easy to find any decimal of PI with a simple formula, [blah blah]

    If only I could make up a nice AskSlashdot to get my story posted, [blah blah]

    --
    "A door is what a dog is perpetually on the wrong side of" - Ogden Nash
  2. Depends *which* NP-Complete problem gets solved by Black+Art · · Score: 1, Troll

    The only thing that would suffer would be algorithms based on that class of problems. Unless someone found a way of solving the entire class of NP-Complete problems. By their nature, i seriously doubt if it is possible to solve beyond a single type of problem. It would require some sort of interrelationship between problem sets. If something on that magnitude were found, the benifits would greatly outweigh the drawbacks as we would have made a great leap forward in the understanding of mathematics.

    --
    "Trademarks are the heraldry of the new feudalism."
  3. Re:Not likely to find that P=NP by The+Cookie+Monster · · Score: 1, Troll

    Yes, it appears many people here seem to think the challenge is finding a P=NP solution.

    We pretty much know that P != NP, we just can't prove it, the challenge is proving P != NP, not finding a P=NP solution.

    Similarly, we know there are an infinite number of primes, just that nobody has been able to prove it.

    Saying things like "So if (when) the time comes" with regard to finding a P=NP solution is somewhat akin to saying if (when) we can finally prove that the primes are finite...

    Sure, it's somewhat fun to speculate on what the social implications might be, but why stop with P=NP, why don't we have an ask slashdot about how you would go public if (when) you discover the fountain of youth?

  4. Re:AI by phliar · · Score: 0, Troll
    First off, if they found an O(n) algorithm, that means that all NP problems would be in linear time.
    Sorry, this is false.

    --
    Unlimited growth == Cancer.
  5. what would i do with a solution to.... by stak · · Score: 0, Troll

    Two women at the same time.