Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Is it $\mathsf{NP}$-hard to decide whether $\mathsf{P}=\mathsf{NP}$ ?

If so, what are the implications ? Is there result suggesting that it is the case ?

share|improve this question
1  
Do you really mean whether P = NP is Turing-decidable? By arguing a problem is NP-hard, we mean it is hard to solve "the instances" of a problem given their sizes. –  Strin Jan 5 '13 at 5:33
add comment

3 Answers

up vote 7 down vote accepted

A similar question is this:

Is $(a \vee \neg b) \wedge (\neg a \vee b)$ $\mathsf{NP}$-hard?

The question itself doesn't make much sense, as $\mathsf{NP}$ (as well as $\mathsf{NP}$-hard) defines a set of languages, but $(a \vee \neg b) \wedge (\neg a \vee b)$ is (just like $\mathsf{P} = \mathsf{NP}$) a word, an element of a language, not a language itself.

But all in all... one can say that it is generally hard to prove (or disprove) $\mathsf{P} = \mathsf{NP}$, it might even be impossible (as discussed in the answer by Jernej).

share|improve this answer
add comment

You have to first understand what is the problem here. A problem is usually a relation between inputs and outputs. The complexity is a measure of difficultly for algorithms to obtain input from the output. A single instance of a problem like the one you have are trivial, since there exists an algorithm that would output the answer (whether it is provable, refutable, or neither). However from the practical point of view this is not of much use.

Asking for $\mathsf{NP}$-hardness of an instances is a confusion that is not uncommon among non-experts in theoretical computer science. The reason for this confusion is that in algorithms/complexity courses, many students mistakenly view $\mathsf{NP}$-hardness as "not solvable in practice" or "no algorithm". $\mathsf{NP}$-hardness does NOT mean that the instances of the problem cannot be solved in practice (take for example SAT), it neither means that there are no algorithms, and it doesn't even mean that there is no efficient/polynomial time algorithm for the problem ($\mathsf{P}$ vs. $\mathsf{NP}$ is still an open problem in theoretical computer science and it doesn't seem that we are close to answer it).

I am guessing that what you really want to ask is if it is possible to use computer to find the answer to $\mathsf{P}$ vs. $\mathsf{NP}$. But this is not a very precise question: what do we mean by using computers to solve an instance of a problem?

Let me try to clarify this: assume that I know the answer to the question, and I write a one line program that always outputs the same correct answer (e.g. the answer to the question is YES and my program is cout<<"YES";). Do we consider this as using computers to find the answer to the question? I would assume no.

Another situation to understand the issues: assume that I have a brute-force algorithm and it finds the answer after say 1 billion years. It is an answer after a finite time, so it is a constant time algorithm However it is not really useful for us, since presumably we want to know the answer in a reasonable amount of time (say before we die). What is a reasonable amount of time? It is not a precise concept.

In summery,

  • a problem instance cannot be $\mathsf{NP}$-hard, an problem instance is trivial from complexity perspective (there exists an algorithm that outputs the correct answer in constant time, we know it is one of the 3 programs (always output "YES", always output "NO", always output "UNDECIDABLE") but we don't know which of these 3 programs correctly solves the problem.

  • $\mathsf{NP}$-hardness is a theoretical concept for a general instance of problems, it doesn't imply that we cannot solved a problem on instances we care about in practice (SAT is $\mathsf{NP}$-hard but in practice SAT-solvers work amazingly well on instances that some industries case about and understanding why this is the case is an on-going research topic).

  • in practice often we don't care about general inputs, we care about a specific subclass of inputs, and on those inputs we might be able to solve the problem. However we should understand that our algorithm will not work on general examples. Any algorithm that works well on some subsets of inputs needs to exploit some properties of those inputs. If we don't have any idea about the particular properties of our instance then we are in a situation similar to the general case inputs.

  • when we don't know any particular property of an instance of a problem we think of it at that time as being hard as general case.

One final point: even if $\mathsf{P}=\mathsf{NP}$ and we can solve SAT and proof search for proofs of a given length efficiently (given $\varphi$ and $n$, is there a proof of length $n$ for $\varphi$ in theory $T$, think of $T$ as ZFC for simplicity), it is possible that it won't help much with finding a proof of that fact for various reasons, e.g.:

  • although the statement is true, there is no proof of it, so current axioms of mathematics are incapable of settling the question positively or negatively,

  • we have an efficient algorithm for searching for proofs of given length, however the constants in the running time of the algorithm are huge, so even though the algorithm is polynomial time, it is not a practical algorithm (e.g. running time is $10^{1000}n^{500}$).

And similarly if $\mathsf{P}\neq\mathsf{NP}$, it doesn't mean that there isn't a short proof of this particular statement in $T$.

However there is a point here as Godel wrote in his famous letter to von Neumann, if there is an algorithm that running in time say $n^2$ that checks if there is a proof of length $n$, then we can run this algorithm with a large enough $n$ such that we are sure no human being can find a proof longer than that. In other words, if the algorithm doesn't solve the problem by either finding a proof or refutation of that size, then there is no answer that can be obtained by humans. So it is undecidable in practice for humans although it might be provable or refutable.

See also my answer on MSE to Solving P vs NP with computer.

share|improve this answer
    
Great answer. Much better than the similar answer I was in the middle of writing. –  Peter Shor Jan 5 '13 at 12:55
    
Thank you @Peter for your kind words. –  Kaveh Jan 30 '13 at 11:16
add comment

It can be the case that there is no proof of $\mathsf{P} = \mathsf{NP}$ and no proof of $\mathsf{P} \ne \mathsf{NP}$. Hence there will be no algorithm to decide whether $\mathsf{P} \overset{?}{=} \mathsf{NP}$.

So we don't kniw if there is a proof for $\mathsf{P} = \mathsf{NP}$ or $\mathsf{P} \neq \mathsf{NP}$, let alone an algorithm to decide if the equality holds or not (in a way proofs are algorithms).

So there is not much sense in discussing the complexity of such an algorithm (if it exists).

share|improve this answer
3  
We don't need Gödel's Incompleteness Theorem for this. The Continuum Hypothesis also has no proof and no disproof, for reasons having no apparent connection to Gödel's work. –  Niel de Beaudrap Jan 3 '13 at 20:56
    
@NieldeBeaudrap Are you aware that Gödel actually provided the first part of the proof that the Continuums Hypothesis is independent of ZFC? Are you further aware that Gödel actually believed that there is a correct answer to the CH, and continued throughout his life to look for better axioms of set theory? (Some believe that the large cardinal axioms might actually provide what Gödel was looking for). –  Thomas Klimpel Jan 3 '13 at 21:16
    
@Jernej If we are not sure whether there is a proof at all, then I think it even make more sense to start by showing that there is no polynomial-size proof, and hence NP-hard. –  eig Jan 3 '13 at 21:59
3  
@ThomasKlimpel: okay, I wasn't precise enough --- obviously not all of Gödel's work is irrelevant. But I'm afraid that apart from not being contemporaries at all, Gödel and I have irreconcilable differences in philosophy of mathematics, so his opinions on whether there's a right answer is somewhat irrelevant. Not to mention that whether there is a right answer to the CH would not have any bearing on the P versus NP problem. Ironically enough for your answer, though, if P versus NP were independent of ZFC, wouldn't this suggest that there are no polytime algorithms for NP? –  Niel de Beaudrap Jan 3 '13 at 22:42
    
@NieldeBeaudrap Stating the unspeakable, "of course P != NP, the question is just how to prove it". Now assume that there is a proof of P != NP which makes use of the "fact" that almost all prime numbers are random in a certain sense which expresses itself in observations like the Riemann hypothesis. We can neither prove that "fact" nor its observable consequences. Axiomatic first order systems produce structures which are more related to topologies than to $\sigma$- algebras (especially not closed under complement), so their shortcomings could be related to the unprovability –  Thomas Klimpel Jan 3 '13 at 23:22
add comment

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.