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

Question

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.

Wishbone

I don't think there ever will be such a proof... :( – Zoraidazorana

Yes perhaps that's true. But if a proof were to exist.... – Wishbone

It's considered much more likely that there will be an explicit disproof of the theory, nowadays. – Cheston

This post makes me feel like an idiot :P – Bouzoun

Answer 1

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

Coniine

For the P!=NP case, why is it enough to show that 3SAT has no polynomial algorithm? There are many other NP complete problems. – Wishbone

Fair point. I think many NP complete problems have polynomial time reductions to other NP complete problems, so maybe it's a matter of similar proofs to other problems that most reduce to. – Coniine

It would be enough to show that e.g. 3SAT has no polynomial-time algorithm. Then for any other NP-complete problem X, 3SAT is polynomial-time reducible to X, so if X has a polynomial-time algorithm, 3SAT would have one via reduction to X. See en.wikipedia.org/wiki/… – Dodecanese

All NP-complete problems reduce to every other NP-complete problem in polynomial time. So a proof for any of these problems is sufficient. – Filiano

saobi: that's what the 'complete' part of np-complete means - solve one in polynomial time, and you have a solution for all of them – Garnetgarnett

I think everyone is in agreement on the P=NP case. But in the P!=NP case, does proving one doesn't have a polynomial solution mean that others don't have a polynomial time solution or does it mean that you could theoretically choose another NP problem to reduce to that in polynomial time and then there would be a chance that one had a polynomial time solution. I think that's what Saobi was getting at. – Coniine

@Jeff, Assumptions: E1 is P, E2 is NP. Both E1 and E2 are np-complete. Because They are both NP complete, There exists a transformation P, such that P(E2) = E1. P takes polynomial time. However, we now have a way of solving E2 in polynomial time. Therefore it is P. Contradiction. Therefore, if E1 is P, then E2 can not be NP. – Slick

@sharth In my example of P!=NP, I was showing what a proof might look like that proved there was no polynomial time algorithm for E1. How would your logic work if we couldn't find any E in P? Just because we can't find one isn't a proof. I was showing a hypothetical case where we proved one NP problem cannot have a P solution. I think Saobi was indicating that just because E1 is NP and has no P solution, how would you use this to prove that E2 also has no P solution? Just to be clear, please explain how it would work assuming we had no E in P. – Coniine

I suppose you could make an argument saying that "since 3SAT is a known NP problem and there is provably no P solution for it, we have found one counter example and thus you cannot conclusively say that P=NP thus we have a sort of P!=NP conclusion." I just don't know how strong of an argument this is. – Coniine

@jeff, that is a perfectly solid argument. if x is in set A and x is not set B, then they are not equal. And since P is a subset of NP, you can only hope to find such an 'extra' element in NP (not P). – Partnership

You know, if you just fill in the "..."s you could easily have the most upvoted SO answer ever! – Antique

@Antique I have discovered a truly marvelous proof of this, which this comment is too narrow to contain. :) – Coniine

Answer 2

Call me pessimistic, but it will be like this:

...

∴, P ≠ NP

QED

Shelve

Answer 3

There are some meta-results about what a P=NP or P≠NP proof can not look like. The details are quite technical, but it is known that the proof cannot be

• relativizing, which kind of means that the proof must make use of the exact definition of Turing machine used, because with some modifications ("oracles", like very powerful CISC instructions added to the instruction set) P=NP, and with some other modifications, P≠NP. See also this blog post for a nice explanation of relativization.

• natural, a property of several classic circuit complexity proofs,

• or algebrizing, a generalization of relativizing.

Kilkenny

Answer 4

It could take the form of demonstrating that assuming P ≠ NP leads to a contradiction.

Orchardman

Answer 5

It might not be connected to P and NP in a straightforward way... Many theorems now are based on P!=NP, so proving one assumed fact to be untrue would make a big difference. Even proving something like constant ratio approximation for TS should be enough IIRC. I think, existence of NPI (GI) and other sets is also based on P!=NP, so making any of them equal to P or NP might change the situation completely.

IMHO everything happens now on a very abstract level. If someone proves anything about P=/!=NP, it doesn't have to mention any of those sets or even a specific problem.

Stepdame

If they are based on P!=NP, they aren't theorems, they are still conjectures. /pedant – Exist

@Exist They are theorems. A theorem is any statement that follows from a set of axioms and pre-existing theorems, yes? Just take P != NP as an axiom, poof. Of course one might argue something about how axioms must be commonly-accepted and P!=NP is not, but... – Versicular

And that is the common argument. Generally the way they turn these types of things into theorems is stating them in a way that includes the P = NP or not hypothesis. However, that doesn't make them true as theorems unless all the hypotheses are true, effectively making such theorems useless except as counterexamples. – Exist

@Exist If the hypotheses of a theorem are always false then that theorem is vacuously true. It'd still be useless, but not false. Just nitpicking. – Indurate

Answer 6

Probably it would be in the form of a reduction from an NP problem to a P problem. See the Wikipedia page on reductions.

OR

Like this proof proposed by Vinay Deolalikar.

Scincoid

Answer 7

The most straightforward way is to prove that there is a polynomial time solution to the problems in the class NP-complete. These are problems that are in NP and are reducable to one of the known np problem. That means you could give a faster algorithm to prove the original problem posed by Stephen Cook or many others which have also been shown to be NP-Complete. See Richard Karp's seminal paper and this book for more interesting problems. It has been shown that if you solve one of these problems the entire complexity class collapses. edit: I have to add that i was talking to my friend who is studying quantum computation. Although I had no clue what it means, he said that a certain proof/experiment? in the quantum world could make the entire complexity class, i mean the whole thing, moot. If anyone here knows more about this, please reply.

There have also been numerous attempts to the problem without giving a formal algorithm. You could try to count the set. Theres the Robert/Seymore proof. People have also tried to solve it using the tried and tested diagonlization proof(also used to show that there are problems that you can never solve). Razborov also showed that if there are certain one-way functions then any proof cannot give a resolution. That means that new techniques will be required in order to solve this question.

Its been 38 years since the original paper has been published and there still is no sign of a proof. Not only that but lot of problems that mathematicians had been posing before the notion of complexity classes came in has been shown to be NP. Therefor many mathematicians and computer scientists believe that some of the problems are so fundamental that a new kind of maths may be needed to solve the problem. You have to keep in mind that the best minds human race has to offer have tackled this problem without any success. I think it should be at least decades before somebody cracks the puzzle. But even if there is a polynomial time solution the constants or the exponent could be so large that it would be useless in our problems.

There is an excellent survey available which should answer most of your questions: http://www.scottaaronson.com/papers/pnp.pdf.

Resilience

Good article on Quantum Computing: scientificamerican.com/… This states that QC cannot solve NP-complete problems, or at least will not "collapse the complexity class". – Deactivate

Answer 8

Certainly a descriptive proof is the most useful, but there are other categories of proof: it is possible, for example, to provide 'existence proofs' that demonstrate that it is possible to find an answer without finding (or, sometimes, even suggesting how to find) that answer.

Flock

Answer 9

Set N equal to the multiplicative identity. Then NP = P. QED. ;-)

Napery

Also, if P is the zero element, then 0N = 0. Now, we can claim the prizes together :) – Kickback

Answer 10

It would likely look almost precisely like one of these

Plop

Answer 11

Good question; it could take either form. Obviously, the specific algorithm would be more helpful, yes, but there's no determining that that would be the way that a theoretical P=NP proof would occur. Given that the nature of NP-complete problems and how common they are, it would seem that more effort has been put into solving those problems than has been put into solving the theoretical reasoning side of the equation, but that's just supposition.

Pellegrini

Answer 12

Any nonconstructive proof that P=NP really is not. It would imply that the following explicit 3-SAT algorithm runs in polynomial time:

Enumerate all programs. On round i, run all programs numbered less than i for one step. If a program terminates with a satisfying input to the formula, return true. If a program terminates with a formal proof that no such input exists, return false.

If P=NP, then there exists a program which runs in O(poly(N)) and outputs a satisfying input to the formula, if such a formula exists.

If P=coNP, there exists a program which runs in O(poly(N)) and outputs a formal proof that no formula exists, if no formula exists.

If P=NP, then since P is closed under complement NP=coNP. So, there exists a program which runs in O(poly(N)) and does both. That program is the k'th program in the enumeration. k is O(1)! Since it runs in O(poly(N)) our brute force simulation only requires

k*O(poly(N))+O(poly(N))^2

rounds once it reaches the program in question. As such, the brute force simulation runs in polynomial time!

(Note that k is exponential in the size of the program; this approach is not really feasible, but it suggests that it would be hard to do a nonconstructive proof that P=NP, even if it were the case.)

Embosom

Answer 13

An interesting read that is somewhat related to this

Refrigeration

Answer 14

To some extent, the form such a proof needs to have depends on your philosophical point of view (= the axioms you deem to be true) - e.g., as a contructivist you would demand the construction of an actual algorithm that requires polynomial time to solve an NP-complete problem. This could be done by using reduction, but not with an indirect proof. Anyhow, it really seems to be very unlikely :)

Shul

Answer 15

The proof would deduce a contradiction from to the assumption that at least one element (problem) of NP isn't also an element of P.

Literal