2
$\begingroup$

Let f be a polynomial-time reduction of a decision problem A to a decision problem B. We know that, if B $\in$ P then A $\in$ P. Similarly, if B $\in$ NP then A $\in$ NP. However, what about the other direction? Assume that A $\in$ NP and consider the following non-deterministic algorithms to decide whether y $\in$ B:

  1. "Guess" non-deterministically some x.
  2. Verify that f(x) = y by computing f(x) in polynomial time and comparing it with y. If f(x)$\neq$y, reject.
  3. Check (using the polynomial-time nRAM for A) whether x $\in$ A and return the answer.

Why does this not qualify as a proof that B $\in$ NP?

$\endgroup$
  • $\begingroup$ You're assuming that $f$ is onto, which is almost never the case. When it is the case, you are correct. $\endgroup$ – Shaull Mar 11 '14 at 10:02
2
$\begingroup$

For your proof to work correctly, $f$ must be surjective:

\begin{align} f: \Sigma_A^\star \to \Sigma_B^\star \\ \forall y \in \Sigma_B^\star \quad \exists x \in \Sigma_A^\star: f(x) = y \end{align}

Otherwise, you cannot guess a $x$ for each $y \in \Sigma_B^\star$, with $f(x) = y$ in step 1.

Alghough some polynomial reductions are bijective (e.g. CLIQUE $\le_p$ INDEPENDENTSET), a polynomial reductions is not required to be either injective or surjective. This is why your proof fails. There are even proofs that use reductions, whose image only consist of two words.

Example for such an extreme case: Proove that $L_1, L_2 \subseteq \Sigma^\star$, where $L_2 \ne \emptyset$ and $L_2 \ne \Sigma^\star$, both $L_1$ and $L_2$ are in $P$ implies that there exists a polynomial reduction from $L_1$ to $L_2$.

Let $w_t \in L_2$ and $w_f \in \Sigma^\star \setminus L_2$. Construct $f: \Sigma^\star \to \Sigma^\star$, such that \begin{align} f(x) = \begin{cases} w_t & \mbox{if } x \in L_1\\ w_f & \mbox{if } x \notin L_1 \end{cases} \end{align} Since $L_1$ is in $P$, $f$ simply calls a TM that decides $L_1$ and then outputs the corresponding words. Therefore, $L_1 \le_p L_2$.

$\endgroup$
0
$\begingroup$

The simple answer to the question in the title is no. By the time hierarchy theorem, we know that NEXPTIME $\neq$ NP but any problem $A$ in NP can be reduced to any NEXPTIME-complete problem $B$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy