# If $P \ne NP$, is every language not contained in $NP$ $NP$-hard?

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!

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

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.

-
@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 '14 at 9:27
Excellent point. I stand corrected! – templatetypedef Jan 17 '14 at 16:57

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.

-

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.

-
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

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.

-
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