Tag Info

4

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

2

Let $F$ be a function that maps integers from $0 \dots N-1$ to $\{0, 1\}$. We want to find $x$ (which is promised to be unique) such that: $$F(x) = 1$$ Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output: $b$, if $F(a) = 0$ $a$, if $F(a) = 1$ For any fixed $x$ and $y$ we have: P_{a=x} = P_{b=x} = P_{a=y} = P_{b=y} = \frac{1}{N}...

1

The accepted answer is incorrect: 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 ...

Only top voted, non community-wiki answers of a minimum length are eligible