106
$\begingroup$

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction.

I know that there are approaches that have been proven to not work, and there are probably more that have a history of failing. There also seem to be so-called barriers that many proof attemps fail to overcome.

We want to avoid investigating into dead-ends, so what are they?

$\endgroup$
5
  • 19
    $\begingroup$ I think this is better to be community wiki (because there is no unique answer to this question, it's too broad). $\endgroup$
    – user742
    May 17, 2012 at 10:03
  • 6
    $\begingroup$ @SaeedAmiri No. Community wiki used to be an alibi to allow questions that weren't suitable for the Stack Exchange platform, but this is no longer done. $\endgroup$ May 17, 2012 at 16:15
  • 4
    $\begingroup$ Moderator note: this question is broader than a normal Stack Exchange question, but we are trying to build a canonical question and answer pair. If you think this question should not exist in its present form, please discuss it on our meta site. $\endgroup$ May 17, 2012 at 19:44
  • $\begingroup$ for a similar question from the opposite/constructive side see how can computer science theories and inquiries be resolved? $\endgroup$
    – vzn
    Jun 6, 2013 at 18:10
  • 5
    $\begingroup$ Wag answer: arXiv is a treasure trove of ways not to do it. $\endgroup$
    – Pseudonym
    Mar 25, 2014 at 3:56

5 Answers 5

82
+150
$\begingroup$

I'd say the most well known barriers to solving $P=NP$ are

  1. Relativization (as mentioned by Ran G.)
  2. Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs.
  3. Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize cannot separate $P$ and $NP$

Another one I'm familiar with is the result that no LP formulation can solve TSP (It was proved by Yannakakis for symmetric LPs and very recently extended to general LPs). Here is a blog post discussing the result.

$\endgroup$
2
  • 4
    $\begingroup$ Relevant links: about barriers in general and toy examples. Also, you should be careful with your last sentence, I think it would be wise to include a link to the blog post that explains why the TSP not doable by general LPs result does not prove $P \neq NP$, since people might be confused by the fact that LP is $P$-complete. $\endgroup$ May 17, 2012 at 14:18
  • 1
    $\begingroup$ If you want to improve the answer (it is not quite acceptance-ready as it is), please add short explanations and links to details so the curious reader knows what you are talking about. $\endgroup$
    – Raphael
    Jun 12, 2012 at 14:24
61
$\begingroup$

Note: I haven't checked the answer carefully yet and there are missing parts to be written, consider it a first draft.

This answer is meant mainly for people who are not researchers in complexity theory or related fields. If you are a complexity theorist and have read the answer please let me know if you notice any issue or have an idea about to improve the answer.

Where you can find claimed solutions of P vs. NP

  • There is The P-versus-NP page which has a list of such claims.
  • Articles claiming to resolve the question are regularly posted on arXiv.

Other lists of how not to solve P vs. NP

Lance Fortnow, So You Think You Settled P verus NP, 2009

Scott Aaronson, Eight Signs A Claimed P≠NP Proof Is Wrong, 2010

Polymath page for Deolalikar's paper, where the further readings section has nice list of references about the problem.


How not to approach P vs. NP

Let me discuss "how not to approach P vs. NP" not in the sense of ideas that will not work but in a more general sense. P vs. NP is a easy to state problem (see also my answer here):

NP = P : For every decision problem with a polynomial time verifier algorithm there is an polynomial time algorithm.

or equivalently

There is a polynomial time algorithm for SAT.
SAT can be replace with any other NP-complete problem.

.

Often people oversimplify and overphilosophize the problem and exaggerate the practical importance of the problem (as stated above). Such statements are often meant to give intuition, but they are not in any way a replacement for the actual mathematical statement of the problem.

Theoretical efficiency is not the same as feasibility in practice.

Let me first with exaggerated practical consequences.

I. It is possible that P=NP but it does not help for any problem in practice!

Say for example that SAT is in P but the fastest algorithm for its running time is $2^{2^{64}} n^{65536} + 2^{2^{128}}$. This algorithm is of no practical use.

II. It is possible that P$\neq$NP and we can solve NP-complete problems efficiently.

Say for example that SAT is not in P but has an algorithm with running time $n^{\lg^*\lg^* n}$.

To give an input that would make $\lg^* n > 6$ you have to use more electrons that there are thought to be in universe. So the exponent is essentially $2$.

The main point here is that P is an abstract simple model of efficient computation, worst-case complexity is an abstract simple model of estimating the cost of a computation, etc. All of these are abstractions, but no one in practice would consider an algorithm like the one in (I) above as an efficient algorithm really. P is a nice abstract model, it has nice properties, it makes technical issues easy, and it is a useful one. However like all mathematical abstraction it hides details that in practice we may care about. There are various more refined models but the more complicated the model becomes the less nice it would be to argue about.

What people care about in practice is to compute an answer to the problem for instances that they care about using reasonable amount of resources. There are task dependent and should be taken into consideration.

Trying to find better algorithms for practical instances of NP-hard problems is an interesting and worthy endeavor. There are SAT-solver heuristic algorithms that are used in the industry and can solve practical instances of SAT with millions of variables. There is even an International SAT Competition.

(But there are also small concrete instances that all these algorithms fail and fail quite badly, we can actually prove that all state of art modern SAT-solvers take exponential time to solve simple instances like propositional Pigeonhole Principle.)

Keep in mind that correctness and running time of programs cannot be obtained just from running the program on instances. It does not matter how many instance you try, no amount is sufficient. There are infinitely many possible inputs and you have to show correctness and efficiency (i.e. running time is polynomial) of the program for all of them. In short, you need mathematical proof of correctness and efficiency. If you do not know what is a mathematical proof then you should first learn some basic mathematics (read a textbook discrete math/combinatorics/graph theory, these are good topic to learn about what is considered a mathematical proof).

Also be careful about other claims about P vs. NP and the consequence of its answers. Such claims are often based on similar simplifications.

Complexity theorists do not really care about an answer to P vs. NP!

I exaggerated a bit. Of course we do care about an answer to P vs. NP. But we care about it in a context. P vs. NP is our flagship problem but it is not the ultimate goal. It is an easy to state problem, it involves many fundamental ideas, it is useful for explaining the kind of questions we are interested in to people who are not familiar with the topic. But we do not seek a one bit Yes/No answer to the question.

We seek a better understanding of the nature of efficient computation. We believe that resolving the question will come with such understanding and that is the real reason we care about it. It is part of a huge body of research. If you want to have a taste of what we do have look at a good complexity theory textbook, e.g. Arora and Barak's "Complexity Theory: A Modern Approach" (draft version).

Let us assume that someone comes with an encrypted completely formal proof of P$\neq$NP and we can verify its correctness to a very high degree of confidence by selecting and decrypting a few bits of the proof (see Zero-Knowledge Proof and PCP theorem). So we can verify the claim with probability of error less than a meteor hitting our house, we are quite sure the proof is correct and P=NP, but we do not know the proof. It will not create much satisfying or exciting for us. The formal proof itself will not also be that satisfying. What we seek is not a formal proof, what we seek is understanding.

In short, from a complexity theorist's perspective

P vs. NP is not a puzzle with a Yes/No answer. We seek an answer to P vs. NP because we think it will come a better understanding of the nature of efficient computation. An answer without a major advancement in our understanding is not very interesting.

There has been too many occasions that non-experts have claimed solutions for P vs. NP, and those claims typically suffer from issues that they would not have made if they just read a standard textbook on complexity theory.

Common problems P=NP

The claims of P=NP seem to be more common. I think the following is the most common type. Someone has an idea and writes a program and tests it on a few instances and thinks it is polynomial time and correctly solves an NP-complete problem. As I explained above no amount of testing will show P=NP. P=NP needs a mathematical proof, not just a program that seems to solve an NP-complete problem in polynomial time.

These attempts typically suffer from one of the two issues:

I. the algorithm is not really polynomial time.

II. the algorithm does not solve all instances correctly.

Signs that a P$\neq$NP argument is not correct

[to be written]

How to check that your algorithm does not really work

You cannot show that your algorithm works correctly by testing. But you can show it does not work correctly by testing! So here is how you can make sure that your algorithm is not correct if you are willing to do some work.

First, write a program to convert instances of SAT (in the standard CNF format) to the NP-hard problem that you are solving. SAT is one of the most studied NP-hard problems and reductions from other problems to SAT is typically easy. Second, take the examples that the state of art SAT-solvers struggle with (e.g. take the examples from SAT competition) and feed them to your algorithm and see how your algorithm performs. Try known hard instances like propositional Pigeonhole Principle (and don't cheat by hard-coding them as special cases), cryptographic instances (like RSA Factoring Challenges), random k-SAT instances near the threshold, etc.

Similarly you can check that your algorithm is not efficient. E.g. if you think your algorithm's running time is not $10 n^2$ but it is taking days to solve an instance of say size 1000. Fix the polynomial worst-case running-time upper bound that you think your algorithm has. Take the instances and estimate the time your algorithm will take to solve them and check if matches your estimates.

How to check your algorithmic P=NP idea cannot work

If you do these you will be pretty sure that your algorithm does not work (if it works better than the state of the art SAT-solvers then compete in the next competition and lots of people would be interested in studying your algorithm and ideas).

Now you know it does not really work but that is not enough. You want to know why,

is the reason my algorithm does not work a small issue that can be fixed or is there a fundamental reason why it cannot work?

Sometimes the problem with the algorithm is simple and one can identify what was wrong conceptually. The best outcome is that you understand the reason your idea cannot work. Often it is not the case, your idea does not work but you cannot figure out why. In that case keep in mind:

understanding why some idea cannot work can be more difficult that solving P vs. NP!

If you can formalize your idea enough you might be able to prove a limitations of particular ideas (e.g. there are results that say particular formalizations of greedy algorithm cannot solve NP-complete problems). However, it is even more difficult, and you do not have much chance if you have not read a standard complexity theory textbook.

Sometime there is not even a clear conceptual idea why the algorithm should work, i.e. it is based on some not well-understood heuristics. If you do not have a clear conceptual idea of why your algorithm should work then you might not have much chance in understanding why it does not!

Common problems with P$\neq$NP claims

Although most experts think P$\neq$NP is more likely than P=NP, such claims seems to be less common. The reason is that proving lower-bounds seems to be a harder task than designing algorithms (but often proving lower-bounds and upper-bounds are intrinsically related).

Issue 1: the author does not know the definition of P and NP, or even worse does not understand what is a mathematical proof. Because the author lacks basic mathematical training he does not understand when he is told what he is presenting is not a proof (e.g. the steps do not follow from previous ones).

Issue 2: the author confuses "we don't know how" with "mathematical impossibility". For example they make various unjustified assumptions and when asked "why this statement is true?" they reply "how can it be false?". One common one is to assume that any program solving the problem has to go throw particular steps, e.g. it has to compute particular intermediate values, because he cannot think of an alternative way of solving the problem.

[to be completed]

Signs that a P$\neq$NP argument is not correct

[to be written]

How to check your P$\neq$NP idea cannot work

If a claim does not suffer from these basic issues then rejecting it becomes more difficult. On the first level one can find an incorrect step in the argument. The typical response from the author is that I can fix it and this back and forth can go on. Similar to P=NP solutions it is often a very difficult to find a fundamental issue with an idea that can show it cannot work, particularly when the idea itself is informal.

In the best case, if we can formalizes the idea and identify the obstacle that shows the idea cannot work we have proven a new barrier result (this is how attempts to prove P$\neq$NP using circuit lower-bounds lead to the Natural Proofs barrier).

$\endgroup$
3
  • $\begingroup$ As much as I like the P-versus-NP page, I find it annoying that it doesn't keep track of which proofs have been withdrawn by their authors. For some of the arXiv links, you find explicit "this paper has been withdrawn" notices on arXiv. I'm pretty sure that there are more withdrawn proofs than just the arXiv papers with explicit notice. OK, I'm aware that withdrawn proofs shouldn't be overstated, because withdrawing an "earlier proof attempt" doesn't imply that the same authors won't try again later. But keeping silent about withdrawn proof attempts still gives a biased impression. $\endgroup$ May 20, 2012 at 12:51
  • 1
    $\begingroup$ @thomas few of the "crank" authors ever "withdraw" their papers. the unspoken point of the woegorgi list is that its distinctly less quality than arxiv papers. but, agreed, wish that woegorgi might add some additional info & that there could be a little more flexible in his editing. for example, he did not put on my P vs NP outline on the list even after emailing him, although recently he posted another item on the fukuyama proof related to a long cstheory.se chat. $\endgroup$
    – vzn
    Jun 6, 2013 at 18:07
  • 1
    $\begingroup$ I appreciate that you are revisiting this! Seems like I prematurely awareded the bounty to the wrong person after all. ;) Note that you can use stackedit.io for preparing a post over time. Looking forward to the rest of the post! $\endgroup$
    – Raphael
    Mar 25, 2014 at 8:37
36
$\begingroup$

Maybe the most common technique that cannot be used is relativization, that is, having a TM with oracle access.

The impossibility follows from a paper by Theodore Baker, John Gill, Robert Solovay who show the existence of two oracles (languages), $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \ne \text{NP}^B$.

Thus, if some proof for, say, $\text{P}\ne \text{NP}$ can be relativized, this would mean that for all oracles $O$, $\text{P}^O \ne \text{NP}^O$ which contradicts the existence of $A$.

Specifically, this means diagonalization cannot be used to prove $\text{P} \stackrel{?}{=} \text{NP}$ as those proofs can be relativized, see e.g. these lecture notes.

$\endgroup$
3
  • 1
    $\begingroup$ Just to completely correct, here diagonalization means direct simple diagonalization. See this question $\endgroup$
    – Kaveh
    May 17, 2012 at 2:24
  • 1
    $\begingroup$ So relativization is not the proof technique, but the effect that breaks a proof? Can you give/link to an example of a proof that can be relativized? $\endgroup$
    – Raphael
    May 17, 2012 at 9:48
  • 2
    $\begingroup$ yes, relativization is not a proof technique, it's a property of a proof (not being formal here btw). if the proof works unchanged when all turing machines are substituted with oracle machines, then the proof relativizes. you can convince yourself that the proof of the time hierarchy theorem relativizes in this sense, for example. $\endgroup$ Aug 4, 2012 at 19:11
10
$\begingroup$

I'd suggest reading this blog post by Lance Fortnow:

  1. So You Think You Settled P verus NP You are wrong. Figure it out. Sometimes you can still salvage something interesting out of your flawed proof.
  2. You believe the proof is correct. Your belief is incorrect. Go back to step 1.
  3. Are you making any assumptions or shortcuts, even seemingly small and obvious ones? Are you using words like "clearly", "obviously", "easy to see", "should", "must" or "probably"? You are claiming to settle perhaps the most important question in all of mathematics. You don't get to make assumptions. Go back to step 1.
  4. Do you really understand the P versus NP problem? To show P≠NP you need to find a language L in NP such that for every k and every machine M running in time $n^k$ (n = input length), M fails to properly compute L. L is a set of strings. Nothing else. L cannot depend on M or k. M can be any program that processes strings of bits. M may act completely differently than one would expect from the way you defined L. Go back to step 1.
  5. You submit your paper to an on-line archive. Maybe some people tell you what is missing or wrong in your paper. This should cause you to go to step 1. But instead you make a few meaningless changes to your paper and repost.
  6. Eventually people ignore your paper. You wonder why you aren't getting fame and fortune.
  7. You submit your paper to a journal.
  8. The paper is rejected. If you are smart you would go back to step 1. But if you were smart you would never have gotten to step 7.
  9. You complain to the editor that either the editor doesn't understand the proof or that it is easily fixed. You are shocked a respectable editor or journal would treat your paper this way.
  10. You resubmit the paper, appeal, try other journals all to no avail.
  11. You are convinced "the establishment" is purposely suppressing your paper because our field would get far less interesting if we settle the P versus NP problem so we have to keep it open at all costs.
  12. If I tell you otherwise would you believe me?
$\endgroup$
15
  • 7
    $\begingroup$ The question asks for “approaches that have been proven to not work” and approaches “that have a history of failing,” and this answer does not mention any approach. $\endgroup$ May 17, 2012 at 22:01
  • 6
    $\begingroup$ My point is that because the blog post does not answer the question at all, it is pointless to copy-and-paste it. $\endgroup$ May 17, 2012 at 22:39
  • 7
    $\begingroup$ This does indeed not answer the question. The blog post is a snarky list of of steps the typical P=NP? crank goes through. While entertaining, this does not provide me with specific theories that have been shown to be unable to separate (or collapse) P and NP. $\endgroup$
    – Raphael
    May 20, 2012 at 10:55
  • 5
    $\begingroup$ How about this? This question asks for barriers to proving P != NP. The barriers in this answer (as stated in the comments) are "assuming something", "bad interpretation", "saying something is clear", "believe on something". These barriers are too general in that they are barriers to proving anything and not specifically barriers to proving P != NP. $\endgroup$ Jul 26, 2012 at 12:40
  • 1
    $\begingroup$ the comments while valid are all missing a basic point. the blog was written by lance fortnow, an expert complexity theorist & world authority on the subject; he just came out with a new book on P vs NP Golden Ticket. so he speaks basically from personal experience. $\endgroup$
    – vzn
    Jun 6, 2013 at 18:52
2
$\begingroup$

here is a somewhat obscure/deep/difficult/insider angle/reference/twist relating to approaches via circuits dating from the 1980s originally pointed out to me years ago by Luca Trevisan elsewhere in cyberspace, and also reiterated by Stasys Jukna, author of an excellent reference near to the subject, Boolean Function Complexity: Advances and Frontiers (Algorithms and Combinatorics, Vol. 27).

one can see an earlier trend in some of Razborov's thinking that eventually led to the Natural Proofs paper (so-called "naturalization"). ref [273] is very technical & difficult and does not seem to be cited, built on/expanded, or reiterated much by later papers/books although Natural Proofs could be seen as a later large generalization. the excerpt is from John E Savages excellent ref Models of Computation p457

Having shown that monotone circuit complexity can lead to exponential lower bounds [270], Razborov [271] then cast doubt on the likelihood that this approach would lead to exponential non-monotone circuit size bounds by proving that the matching problem on bipartite graphs, a problem in P, has a super-polynomial monotone circuit size. Tardos [324] strengthened Razborov’s lower bound, deriving an exponential one. Later Razborov [273] demonstrated that the obvious generalization of the approximation method cannot yield better lower bounds than $\Omega(n^2)$ for Boolean functions on $n$ inputs realized by circuits over complete bases.

[270] A. A. Razborov, “Lower Bounds on the Monotone Complexity of Some Boolean Functions,”Dokl. Akad. Nauk SSSR (Soviet Math. Dokl.) 281 (1985), 798–801, (in Russian); English translation in Soviet Math. Dokl. 31 (1985), 354–357

[271] A. A. Razborov, “A Lower Bound on the Monotone Network Complexity of the Logical Permanent,” Mat. Zametki 37 (1985), 887–900, (in Russian); English translation in Math. Notes 37 (6) (1985), 485–493.

[273] A. A. Razborov, “On the Method of Approximations,” Proc. 21st Ann. ACM Symp. Theory of Computing (1989), 167–176.

$\endgroup$
5
  • 2
    $\begingroup$ I don't see how this answers the question "how not to prove P?=NP". Right now, it seems more like some kind of speculation about someone's thoughts. $\endgroup$
    – Juho
    Jun 6, 2013 at 18:51
  • $\begingroup$ huh?!? @juho sorry, its not obvious? [monotone] circuits were once thought as a viable or even leading candidate to prove P$\neq$NP by many [some even still think so], an approach apparently pioneered by Sipser, eg see circuit complexity, and these papers are some crucial ones on the subj & show a/the [key] historical shift in thinking/conventional wisdom. $\endgroup$
    – vzn
    Jun 6, 2013 at 19:01
  • 2
    $\begingroup$ Sure, I'm only suggesting to make all of this explicit. Circuit complexity is not even undergrad level material, so some background is justified. It is fair to expect the reader not to be an expert in complexity theory. $\endgroup$
    – Juho
    Jun 6, 2013 at 21:00
  • $\begingroup$ @juho ok. once saw the Savage book [which is very "circuit-centric"] used in an undergraduate level class, it surprised me too. agreed its advanced material hence the wording of the 1st sentence. as for "speculation on thoughts", there is none, except citing Razborovs own thoughts as written/recorded in his own papers. $\endgroup$
    – vzn
    Jun 6, 2013 at 22:02
  • 1
    $\begingroup$ and by the way, overall this is a very advanced question (not really undergraduate level) and other responses are advanced & generally outside of undergraduate level. $\endgroup$
    – vzn
    Jun 7, 2013 at 15:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.