patternModerate
Do any decision problems exist outside NP and NP-Hard?
Viewed 0 times
anyhardexistdecisionoutsideandproblems
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#11009, answer score: 14
Revisions (0)
No revisions yet.