Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The other day, a student asked me whether, if $P \ne NP$, whether any language outside of $NP$ is known to be $NP$-hard. I wasn't sure if

  • This is definitely known to be true,
  • This is definitely known to be false, or
  • This depends on another set of complexity assumptions that do not immediately follow from $P \ne NP$ (that is, even if we knew $P \ne NP$, this would still be an open question)

None of the texts on complexity I looked into seemed to answer this question (though it is quite possible that I simply missed it). Does anyone know which of the above three is true, or know a good reference where I could look up the answer?

(Note: This earlier question is related, but I'm considering solely questions outside of $NP$ (so the existing answer doesn't really help) and am not restricting this to just the decidable languages)

Thanks!

share|improve this question
    
I think that it's the case that this is definitely known to be true, but I'm not certain enough to make this an answer. –  Keith Irwin Dec 13 '11 at 6:24
1  
The answer to this question should not depend on wether P=NP. –  Raphael Dec 13 '11 at 6:58
    
Are you asking if every language outside NP is NP-hard? Or are you asking if there exists some language outside NP that is NP-hard? I cannot tell from the wording... –  Srivatsan Dec 13 '11 at 7:26
    
What happens, say, if you take the language of all $x$ such that $|x| \in K$, for some undecidable $K$? –  Yuval Filmus Dec 13 '11 at 7:58
    
@SRivastan- The question is whether every language outside NP is NP-hard. –  templatetypedef Dec 13 '11 at 8:18
show 3 more comments

4 Answers

up vote 6 down vote accepted

So it looks like the answer to this question is as follows: If $P \ne NP$, then there exists a language not contained in NP that is not NP-hard. This follows from Mahaney's theorem, which says that $P = NP$ iff there is some sparse language L such that SAT is polynomial-time reducible to L. In particular, this says that if $P \ne NP$, then SAT is not polynomial-time reducible to any sparse language. So consider the unary halting language $UNARYHALT$ consisting of unary encodings of TM/string pairs where the given TM halts on the particular input. This language is sparse, since for any length there is either zero or one strings in the language with that length. Moreover, this language is undecidable by a reduction from the halting problem, so it cannot be in NP. Therefore, if $P \ne NP$, by Mahaney's theorem this language is not NP-hard, because there is no polynomial-time reduction from SAT to it.

share|improve this answer
add comment

It seems that the probabilistic method works.

Consider $\{0,1\} \times \{0,1\} \times \dots$ as a probability space, corresponding to throwing a coin countably many times (product measure).

Any event $a \in \{0,1\} \times \{0,1\} \times \dots$ encodes a subset $L \subseteq \{0,1\}^{\ast}$, the consecutive bits decide if $\epsilon \in L, 0 \in L, 1 \in L, 00 \in L, \dots$. We will now select random $L$, equivalently random $a$, and check its properties.

With probability 1, $L \notin \mathsf{NP}$ (since $\mathsf{NP}$ is countable), even more: with probability 1, $L$ is undecidable.

Now, suppose you have a reduction $f \colon A^{\ast} \to \{0,1\}^{\ast}$ that attempts to reduce SAT to $L$. Since $\mathsf{P} \neq \mathsf{NP}$ by assumption, the image of $f$ must be infinite; otherwise you could convert the reduction to a decision procedure for $SAT$. However, for any $x$, it must hold $x \in SAT \iff f(x)\in L$, and that happens with probability 1/2. Since there are infinitely many values for $f(x)$, the probability that $f$ is a valid reduction from SAT to $L$ is 0.

Since there are countably many reductions, and countable intersection of sets of measure 1 has measure 1, the overall probability of $L$ satisfying all conditions is 1.

So a "generic" random language is neither decidable nor $\mathsf{NP}$-hard, unless $\mathsf{P} = \mathsf{NP}$.

It is possible to convert this proof to diagonalization: on $2i$-th stage, you diagonalize against $i$-th $\mathsf{NP}$ problem; on $2i+1$-th stage, you diagonalize against $i$-th polynomial time reduction with infinite image. This gives a constructive example; with more careful bookkeeping you can get a decidable example.

share|improve this answer
    
@templatetypedef: No, there's definitely uncountably many NP-hard languages. Pick arbitrary language $L$ and then $M=0\cdot L \cup 1\cdot SAT$ is NP-hard by reduction from SAT to $M$: $f(x) = 1 x$. In your argument, a pair does not specify the NP-hard language completely, outside the image of the reduction. –  sdcvvc Jan 17 at 9:27
    
Excellent point. I stand corrected! –  templatetypedef Jan 17 at 16:57
add comment

The answer to this question depends on the complexity assumptions.

  • If $\mathrm P = \mathrm {NP}$, then every nontrivial language $L$ is $\mathrm{NP}$-hard. [A language is said to be nontrivial if it contains at least one yes instance and at least one no instance.] To reduce a given $\mathrm {NP}$ problem $A$ to $L$, we simply ignore $L$ and use the polynomial-time algorithm for $A$ -- this is guaranteed to exist under our assumption.

  • Assuming $\mathrm{NP} \neq \text{co-}\mathrm{NP}$, no problem in $\text{co-}\mathrm{NP}$ would be $\mathrm{NP}$-hard.

share|improve this answer
    
So even if P != NP, we cannot say for certain whether every language outside NP is NP-hard, since it depends on whether NP = co-NP? It seems like there might be some other known result that would show this result either way. –  templatetypedef Dec 13 '11 at 8:19
    
@templatetypedef Yes, this does not answer your question completely because I need the stronger hypothesis that NP $\neq$ coNP (although most people believe this stronger assumption anyway). –  Srivatsan Dec 13 '11 at 8:30
    
Any co-NP-complete problem, for example the set of Boolean formula tautologies, is NP-hard. The definition NP-hardness allows arbitrary oracle ("Turing" or "Cook") reductions, not just many-one ("Karp") reductions. –  Colin McQuillan Dec 13 '11 at 9:07
    
@Colin, You raise a nice point. Indeed under the Turing (Cook) reductions, coNP-complete problems are NP-complete as well. However, without explicit qualification, I always take NP-complete in the sense of Karp reductions (as my post shows :-)). However I will be happy to see answers from the other point of view. :) –  Srivatsan Dec 13 '11 at 9:16
    
"NP-complete" is always Karp, "NP-hard" is always Turing. –  Colin McQuillan Dec 13 '11 at 9:28
show 7 more comments

Take any undecidable language L and let L' be the language of pairs (n,x) with x in L and n=2^|x| in unary. Then L' is in P/poly but not in NP. If L' is NP-hard then NP$\subset$P/poly and the polynomial hierarchy collapses by the Karp-Lipton theorem.

share|improve this answer
    
This is not a complete answer to the question, however, because we may have NP $\subseteq$ P/poly but P$\neq$NP. –  Colin McQuillan Dec 13 '11 at 9:27
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.