Consequences of a Solution to NP Complete Problems?

Posted by Cliff on Thursday December 13, 2001 @12:22PM 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.

1 of 525 comments (clear)

Min score:

Reason:

Sort:

If I had that O(n) algorithm... by mfarah · 2001-12-13 12:34 · 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