8
$\begingroup$

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard.

In order to be in NP, problems have to have a verifier that runs in polynomial time on a deterministic Turing machine. Obviously, all problems in P meet that criteria, but what about the problems with sub-exponential complexity? They do not belong to P and it's not obvious to me that they all have efficient deciders. And they certainly don't qualify for NP-complete.

I'm willing to believe that all decision problems are either NP or NP-hard or both, but nobody has actually said that (that I can find). I'm also willing to believe that such problems do exist, even if they are very contrived. Maybe someone more knowledgeable can put this issue to rest for me. Thanks.

Edit

I abused the term 'subexponential' in my question. In my mind it meant some problem with a complexity between exponential and polynomial like L-notation in this table. See the links in Raphael's answer for more details.

$\endgroup$
  • $\begingroup$ Do you consider CO-NP to be a set of decision problems? $\endgroup$ – Aryabhata Apr 4 '13 at 5:06
  • 1
    $\begingroup$ Our reference question about notions around NP may be a worthwhile read for you. $\endgroup$ – Raphael Apr 4 '13 at 6:29
  • $\begingroup$ are you familiar with the time hierarchy theorem? it proves that problems of unlimited amount of time complexity exist. in other words the class "NP hard" also applies to "super hard" problems that provably require exponential time. $\endgroup$ – vzn Apr 4 '13 at 18:22
  • $\begingroup$ I know that NP-hard is a huge category. I'm more interested in non-NP-hard problems. Specifically those that are non-NP. $\endgroup$ – Sebastian Goodman Apr 4 '13 at 18:53
11
$\begingroup$

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case.

If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard.

For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this language is not computable, it is clearly outside of $NP$. As this language is sparse, $P \neq NP$ together with Mahaney's theorem implies that it is not NP-hard.

If we want a computable counterexample, we can take a language $L$ that is not in EXPSPACE. We number all finite words in increasing order as $(w_n)_{n \in \mathbb{N}}$, and now consider the language $L' = \{1^n \mid w_n \in L\}$. Again, Mahaney's theorem ensures that $L'$ is not NP-hard. If $L'$ were in NP (or even PSPACE), then an EXPSPACE algorithm for $L$ would be available in "Given w_n, compute 1^n and run the PSPACE-algorithm for $L'$ on it."

See here https://math.stackexchange.com/questions/235162/if-an-unary-language-exists-in-npc-then-p-np for a proof of Mahaney's theorem. Note that Yuval speaks about starting with an NP-complete unary language, that assumption is not used - the argument only needs an NP-hard unary language.

$\endgroup$
3
$\begingroup$

Assuming $P\not=NP$ there are lots of problems incomparable with $SAT$, hence neither $NP$ nor $NP$-hard.

Here's an overkill generalization of this fact:

Suppose $X\not\in P$. Then there is some $Y$ such that $Y$ is incomparable with $X$ under polynomial-time-Turing reducibility (hence a fortiori Karp reducibility).

(So in particular if $P\not=NP$ we get an affirmative answer to the OP.)

One way to prove this is with forcing. Fix an $X\not\in P$ and let $Y$ be sufficiently generic with respect to $X$ ($2$-generic with respect to $X$ is already overkill). Since only countably many things are reducible to $X$, a sufficient level of genericity will ensure that $Y$ is not reducible to $X$. So we only have to treat the possibility that $Y\ge_pX$.

By genericity, if $Y\ge_pX$ there is some condition $\sigma$ (= "finite initial segment" of $Y$, thinking of languages as infinite binary strings) such that for some number $e$ and polynomial $p$, $\sigma$ forces "$\Phi_e$ is a $p$-bounded Turing reduction of $X$ to $Y$." But this lets us compute $X$ in polynomial time as follows: to tell whether $n\in Y$, we just check whether $$\Phi_e^{\sigma^\smallfrown 1^{p(\vert n\vert)}}(n)\downarrow=1,$$ which can be done in polynomial time.

EDIT: note that this argument produces non-decidable languages since "sufficiently generic" languages are not decidable. This is both good and bad: it shows that in a strong way that "hard to compute" and "computes a lot" aren't really the same, but it also means that the examples so produced aren't of general complexity-theoretic interest. Constructing decidable examples takes a finer-grained argument, and Arno's answer does precisely this. In general forcing arguments can often prove very broad results in quite snappy ways, but usually don't result in "nice" objects. The original example of this is probably the fact that forcing can build incomparable $\Delta^0_2$ Turing degrees but we need priority arguments to build incomparable c.e. Turing degrees, but Baker-Gill-Solovay provides another good example since there is - to my knowledge - no known "nice" oracle relative to which we have $P=NP$, despite the existence of such being not too hard to prove via forcing.


The proof above immediately yields a strengthening of the claim: for any $X$, the set of sufficiently generic $Y$s is always comeager, so in a precise sense "most" languages will be incomparable with $X$ as long as $X\not\in P$.

(I strongly suspect the same is true for measure as well, but I don't have an argument at the moment.)

$\endgroup$
0
$\begingroup$

NP contains all (decision) problems that are at most as hard as NP-complete problems with respect to Karp reductions.

NP-hard contains all (decision) problems that are at least as hard as NP-complete problems with respect to Karp reductions.

So, in the "Karp-reduction universe", NP and NP-hard do indeed cover everything. There may be orthogonal problem classes, though: for instance, co-NP-complete are neither in NP nor NP-hard (w.r.t. Karp reductions) if NP does not equal co-NP (which we don't know).

Aside from that, note that there are subexponential algorithms for NP-complete problems, but no known polynomial ones.

Thanks frafl for pointing out a critical flaw in the initial version of this answer. Readers of the old version may want to read this.

$\endgroup$
  • 2
    $\begingroup$ I would say "cover everything comparable to NP" (in the partial order given by polytime Karp reductions; it's important to realize that this partial order is not a total order) $\endgroup$ – Sasho Nikolov Apr 4 '13 at 14:24
  • $\begingroup$ So when you say w.r.t. Karp reductions, you mean problems where it is meaningful to talk about making Karp reductions on them to problems in NP? $\endgroup$ – Sebastian Goodman Apr 4 '13 at 18:55
  • $\begingroup$ @SebastianGoodman: Under NP unequal co-NP, there is no Karp-reduction between NP-complete and co-NP-complete problems in either direction; the classes would be incomparable w.r.t. $\leq_p$, which is not a total order, as Sasho notes. $\endgroup$ – Raphael Apr 4 '13 at 23:28
  • 2
    $\begingroup$ This answer seems to be just plain wrong. $\endgroup$ – Arno Dec 3 '19 at 14:50
  • $\begingroup$ That is so only if $\mathsf{P} \ne \mathsf{NP}$ and $\mathsf{coNP} \ne \mathsf{NP} $ (as is widely believed, but not proven). $\endgroup$ – vonbrand Feb 5 at 23:38
-1
$\begingroup$

The answer is (trivially) yes. Any non-decidable language provides a decision problem that is harder than anything in NP.

$\endgroup$
  • 1
    $\begingroup$ This is incorrect: "not easier" is not the same as "harder," and as I explained in my answer there are non-decidable languages which are not NP-hard ($2$-generic languages are never decidable). $\endgroup$ – Noah Schweber Feb 6 at 20:00
  • $\begingroup$ In fact, per my answer most undecidable languages (that is, comeager-many) are incomparable with NP with respect to polytime Turing reducibility (so not NP-hard) assuming P$\not=$NP. $\endgroup$ – Noah Schweber Feb 11 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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