Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|cite|improve this question
30  
This question is ill-posed. Since only one of the statements can be true, one is impossible to prove. The other may be possible to prove, and if so it'd be easier to prove than the false one. Ergo, I have no idea what kind of answer you are looking for. Community votes, please! Can this be answered at all? – Raphael Jan 28 at 18:21
10  
@Raphael I'm in disagreement. You could interpret OP's question as "If P = NP were true, would it be easier to prove than proving P ≠ NP if P ≠ NP were true?" I don't think OP seriously intended for it to be construed as a suggestion that both must be true. – The Anathema Jan 28 at 21:40
3  
FWIW, it seems to me that a) @TheAnathema's interpretation of the question is correct and b) it is a meaningful question. In other words: If P=NP, and a proof is found, that proof will probably be in the form of a polynomial-time algorithm for an NP-complete problem. On the other hand, if we start with the assumption that P≠NP, what sorts of techniques could we utilize to find a proof, and what form would such a proof potentially take? – JohannesD Jan 28 at 22:30
1  
    
Comments are not for extended discussion; this conversation has been moved to chat. – Gilles Jan 29 at 18:23
up vote 23 down vote accepted

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.

share|cite|improve this answer
14  
You could interpret OP's question as "If P = NP were true, would it be easier to prove than proving P ≠ NP if P ≠ NP were true?" I don't think OP seriously intended for it to be construed as both being true. – The Anathema Jan 28 at 21:38
6  
@TheAnathema I guess one has to interpret the question that way. But it's still pretty ill-posed because one of the options is necessarily counterfactual. How can you compare that counterfactual with the difficulty of proving something that's true? – David Richerby Jan 29 at 1:24
    
@David, the claim about difficulty of proving P$\neq$NP compared to P=NP is something is I have from experts a number of times. Asking if it is a reasonable claim is a valid question. Assessing the difficulty of counterfactual situations (when they are not known to be so) is common actually. Take e.g. someone asking about difficulty of proving P$\neq$NP. If P$=$NP then it is counterfactual. – Kaveh Feb 2 at 5:32

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
1  
If that "something" exists, it is easier to prove it does (trivially, you can't prove it doesn't exist; that doesn't mean it isn't devilishly difficult to find said proof). Same reasoning the other way around. As comments say, the question itself makes no sense. – vonbrand Jan 29 at 17:15
    
@vonbrand I am not saying for any X: is it easier to prove that X exists or to prove that X does not exist, I am saying that for any X,Y: is it easier to prove that X exists or to prove that Y does not exist. i.e. if E the set of proofs that prove sentences of the form 'X exists' and NE the set of proofs that prove sentences of the form 'Y does not exist', and d(P) the difficulty of the proof, is it true that d(X) < d(Y) where X in E and Y in NE. – Thanos Tintinidis Jan 29 at 17:36
    
You'd have to somehow define $d(X)$, and how to average it over all possible $X$. Given that there are an infinite number of $X$, each with an infinite number of proofs, and we know only of a tiny, finite set of $X$ and of those just a selection of proofs, this looks hopeless. I'd be thrilled to be proven wrong, sure. – vonbrand Jan 29 at 17:40
    
@vonbrand yes; moreover, I'm arguing that you cannot use OP's method (keep generating potential solutions until you find one) as an argument for suggesting that proving existence is easier than proving non-existence as you can transform the transform the statement S1 of non-existence to a statement S2 of the existence of the proof of the statement S1. Although I'm starting to doubt the value of this – Thanos Tintinidis Jan 29 at 17:49

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.

share|cite|improve this answer
    
When you talk about defining the question "more religiously", I assume you mean "more rigorously"? :-) – David Richerby Feb 24 at 3:11
1  
@David, yes, auto-correction sometimes does that. :) – Kaveh Feb 24 at 4:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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