HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is $NP$ "minimal", i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#35375, answer score: 3

Revisions (0)

No revisions yet.