Would proving P≠NP be harder than proving P=NP?

Question

Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP.

Let Q be one of known NP-hard problems. To prove P=NP, we need to design a single polynomial time algorithm A for Q and prove that A correctly solves Q.

To prove P$\neq$NP, we need to show that no polynomial time algorithm solves Q. In other words, we have to rule out all polynomial time algorithms.

I have heard people say this makes the second more difficult task (assuming that it is really true).

Is there a reason to think that proving P=NP (assuming that P=NP) would be easier than proving P$\neq$NP (assuming that P$\neq$NP)?

Answer 1

As Raphael explains, this question is ill-posed, since at most one of P=NP and P≠NP should be provable at all. However, a similar question arises in theoretical computer science in several guises, the most conspicuous of which is in the field of approximation algorithms.

Given an NP-hard optimization problem (say, maximization), we can ask how well we can approximate it. Proving an upper bound on the possible approximation is akin to P=NP, while proving a lower bound on the possible approximation is akin to P≠NP. The former is much easier than the latter. Indeed, to prove an upper bound all one has to do is to come up with an approximation algorithm and analyze it. In contrast, all known lower bounds are conditional: they are valid only if P≠NP (indeed, if P=NP then every NP-hard optimization problem would become solvable). To prove these lower bounds, we show that if we could approximate the problem too well, then we would obtain a polynomial time algorithm for some NP-hard problem. Usually this is done via the intricate technical machinery of the PCP theorem. This field, known as hardness of approximation, can be approached only be specialists, and is technical more challenging than most approximation algorithms. So in this case at least, P=NP is indeed easier than P≠NP.

Answer 2

Well you basically have the idea. We generally think that P != NP but have no idea how we would even prove these things are not equal.

Conversely, if P = NP, you'd think we would have found an algorithm to solve one of the dozens of NP-complete problems by now.

These are very hand-wavey arguments but in a couple sentences they describe the culture among computer scientists.

Whether proving P != NP is "harder" of course depends on which is true though (barring meta-mathematical results?), and that, of course, we do not know.

Answer 3

We have not ruled out the possibility of a simple proof that P=NP. If someone tomorrow comes up with an algorithm that solves a NP-complete problem in P time, the world changes.

On the other hand, we have ruled out the possibility of a simple proof that P!=NP. Our typical proof techniques for showing that two different complexity classes have been formally proven insufficient. Three such techniques are known as "arithmetization", "natural proof"s, and the category of proofs called "relativizing" (ones that do not care what oracles are in use). It can be proven that any proof technique that falls into any 3 of those categories cannot prove P!=NP.

In effect, there is strong evidence that proving P!=NP requires new kinds of proof (new techniques with different properties), not just novel application of well-known proof techniques.

---

Now, it might turn out that P=NP, while there is no simple to verify algorithm in P that solves an NP-complete problem, and that novel proof techniques are required to prove P=NP. (If P=NP, we already know algorithms that are technically in P that solve NP-hard problems, amusingly. They are not practical to run, as their constant factor is large.)

Basically, we know a lot about what we cannot use to prove P!=NP, while we seemingly know little about what we cannot use to prove P=NP.

Answer 4

I think that the question can be reduced to: is it easier to prove that something exists or to prove that something does not exist.

The argument in favour of proving that something exists is that it's easy to construct things that might satisfy the requirements and it's also easy to check if they indeed satisfy them.

In some cases this is true: if you want to find the root of a polynomial, it's easy to construct numbers and it's easy to check if they are roots.

The problem, of course, is that you have to be lucky. You might be able to reduce the search space, e.g. by proving that it must be a multiple of 5 or between 1 and 10; but, unless you limit it to a finite set of numbers (in which case you are not really using the "guess and validate" method), you don't have a method for solving the problem: you only have a method that, assuming you are extremely lucky, might generate a solution.

But if you want that, it's equally easy to prove that something does not exist! Generate texts that could be possible solutions and check if they actually are.

Therefore, having a method that might yield the solution by pure luck does not mean that proving that something exists is easier.

Now, is it generally easier to prove that something exists with some other method? It depends on the actual problem because otherwise proving that something does not exist would be reduced to proving that a proof that it doesn't exist exists. And I'm afraid that we cannot measure that as there never was something that was proven to both exist and not exist so we can (attempt to) measure the difficulty of the proof.

Answer 5

There are some experts who believe that proving P$\neq$NP is a harder than proving P=NP in the sense of the time that they think it will take to settle the P vs. NP question. But that is mostly some intuition based on the feeling that it is easier to design algorithms for problems than proving that there are no (efficient) algorithms. Generally we have not been very successful in proving lower bounds for problems. We cannot even rule out a linear time algorithm for SAT. We cannot rule out that there isn't a log space algorithm for SAT. We cannot even show that there isn't polynomial size Boolean circuit of constant depth with $\land$, $\lor$, $\lnot$, and $\mod_6$ gates that cannot solve SAT (in layman's terms it is possible that there is a constant time parallel algorithm with polynomial number of processors that solves SAT and each process computing only one of these gates). The best lower bounds we have for Turing machines solving SAT cannot even show that there isn't an algorithm whose running time multiplied by the space it uses is $n^{1.9}$. I can go on quite a bit about the quite embarrassing state of proving lower bounds (but keep in mind that we also have barrier results that explain why it is so difficult to prove lower bounds). Some experts think Ketan Mulmuley's GCT program is the most likely to resolve P vs. NP and Mulmuley himself has repeated said that he believes it will probably take over a hundred year to get there.

However there has been some recent work by Ryan Williams and others that show that there are intrinsic links between proving lower bounds and finding algorithms. E.g. he showed that an algorithm slightly better than brute force algorithm for a particular restricted SAT problem implies circuit lower bounds and then he designed such an algorithm. So I think people are a bit less pessimistic and also don't seem developing algorithm and proving lower bounds as separate as people used to think they are.

Now let's go back to the question and try to look at it a bit more religiously. To answer the question we need to formalize what we mean by difficulty of proving a statement. For this we can use proof theory and proof complexity which exactly looks at various ways of defining hardness of proving a statement. So let me give a short explanation of what is proof complexity is about. A proof system is essentially a verifier algorithm for proofs. We give a string $\pi$ and a string $\varphi$ and we ask if $\pi$ is a proof of $\varphi$ and the algorithm returns yes or no. You can think of any proof checker in this way. You can also think of proofs in a mathematical system like ZFC as such. The checking process itself can be done in polynomial time in the size of the proof because it is a syntactic task.

Now consider a formula $\varphi$. What does it mean for $\varphi$ to be hard to prove? One possibility is that the shortest proof of $\varphi$ is very large. If it is too large, say the number of bits required to represent it is larger than $2^{65536}$ then we cannot even state the proof. A second possibility is that the proof is not too large but it is hard to find. Let me explain this a bit: think about a proof search algorithm. Most rules are deterministic in a system like LK in the sense that you can determine the previous lines from the current line in the proof and the rule. An important exception to this is the cut rule. It is important because although we don't need the cut rule for proving statements it can reduce the size of the shortest proof considerably. However cut rule is not deterministic: there is a cut formula that we have to guess. You can think of cut rule as proving lemmas and using them. The cut formula is like a lemma. But what lemma should we prove that will help us? That is the difficult part. Often a result is proven in mathematics by finding a good lemma. Also when you use previously proven results you are essentially using the cut rule. Another important component in proving statements is definitions. Often we define a new concept, then prove statements about it, and finally apply it in our particular case. Using definitions reduces the size of the formulas (try expanding some mathematical formula to the pure set theoretic language by expanding definitions to get an idea of how important definitions are). Again what new definitions should we use? We don't know. This brings me to third meaning of a statement being difficult to prove. A statement can be difficult to prove because you need strong axioms. Take e.g. CH. It cannot be proven in ZFC nor can be refuted in ZFC. This is an extreme case but that happens more often that you think. E.g. do we need large cardinal axioms (to be able to work in Grothendieck universes) to prove FLT or can we prove it in a much weaker theory like PA? This is another concept regarding the difficulty of proving statements.

Now let's go back to P vs. NP. We don't have results that state that the problem cannot be settled one way or another in rather weak arithmetic theories. Alexander Razborov wrote a paper in 1995 titled "Unprovability of Lower Bounds on the Circuit Size in Certain Fragments of Bounded Arithmetic" that showed it is not possible to prove it in some weak theory but the theory is really really weak. To my knowledge there has not been much progress in extending that to considerable stronger theories like Sam Buss's bounded arithmetic theories and even if the result is extended to them they are still far away from something like PA or ZFC. So in short not only we cannot prove that SAT is not in very small complexity classes, we cannot even prove we cannot prove P$\neq$NP in very weak theories. The formal reason we have about why it is difficult to prove P$\neq$NP is barrier results that state that such and such techniques cannot prove by themselves that P$\neq$NP. They are nice results but they don't even rule out the possibility of combining those techniques to show P$\neq$NP.