patternMinor
Is $NP$ "minimal", i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?
Viewed 0 times
implynotinharddoesminimal
Problem
Suppose $\Pi$ is a decidable decision problem.
Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard?
Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim without any unknown assumptions?
Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard?
Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim without any unknown assumptions?
Solution
If $P=NP$ then
$\Pi \not\in NP$
$\implies$
$P=NP$ and $\Pi$ is neither the empty language nor the full language
$\implies$
$\Pi$ is $NP$-hard.
Let $\operatorname{int}(s)$ denote the result of putting a leading 1 on the most significant
end of $s$ and then parsing the result as an integer in binary.
If $P\neq NP$ then for each subset $S$ of $\{0,1\}^*$ that is not in $\operatorname{NTIME}$$\left(2^{O\left(2^n\right)}\right)$,
$\{111 \ldots [2^{\operatorname{int}(n)} \text{ of them}] \ldots 111 : n\in S\}$ is not in NP since $S$ is too hard, is decidable
if and only if $S$ is, and is not NP-hard even with respect to Turing reductions since
for any polynomial bound, there are only polynomially many possibilities for the
subset of that language consisting of the elements that fit within the length bound,
so one could try the search-to-decision reduction with each of them.
$\Pi \not\in NP$
$\implies$
$P=NP$ and $\Pi$ is neither the empty language nor the full language
$\implies$
$\Pi$ is $NP$-hard.
Let $\operatorname{int}(s)$ denote the result of putting a leading 1 on the most significant
end of $s$ and then parsing the result as an integer in binary.
If $P\neq NP$ then for each subset $S$ of $\{0,1\}^*$ that is not in $\operatorname{NTIME}$$\left(2^{O\left(2^n\right)}\right)$,
$\{111 \ldots [2^{\operatorname{int}(n)} \text{ of them}] \ldots 111 : n\in S\}$ is not in NP since $S$ is too hard, is decidable
if and only if $S$ is, and is not NP-hard even with respect to Turing reductions since
for any polynomial bound, there are only polynomially many possibilities for the
subset of that language consisting of the elements that fit within the length bound,
so one could try the search-to-decision reduction with each of them.
Context
StackExchange Computer Science Q#35375, answer score: 3
Revisions (0)
No revisions yet.