New answers tagged complexity-classes
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 ...
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}...
Top 50 recent answers are included
