Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What would a P=NP proof be like, hypothetically?

Would it be an polynomial time algorithm to a specific NP-complete problem, or just abstract reasonings that demonstrate solutions to NP-complete problems exist?

It seems that the a specific algoithm is much more helpful. With it, all we'll have to do to polynomially solve an NP problem is to convert it into the specific NP-complete problem for which the proof has a solution, and we are done.

like image 635
Saobi Avatar asked May 22 '09 22:05

Saobi


2 Answers

P = NP: "The 3SAT problem is a classic NP complete problem. In this proof, we demonstrate an algorithm to solve it that has an asymptotic bound of (n^99 log log n). First we ..."

P != NP: "Assume there was a polynomial algorithm for the 3SAT problem. This would imply that .... which by ..... implies we can do .... and then ... and then ... which is impossible. This was all predicated on a polynomial time algorithm for 3SAT. Thus P != NP."

UPDATE: Perhaps something like this paper (for P != NP).

UPDATE 2: Here's a video of Michael Sipser sketching out a proof for P != NP

like image 111
Jeff Moser Avatar answered Oct 12 '22 04:10

Jeff Moser


Call me pessimistic, but it will be like this:

...

∴, P ≠ NP

QED

like image 17
Thanatos Avatar answered Oct 12 '22 02:10

Thanatos