-1
$\begingroup$

I know it is true that if A is not in P, and A reduces B, then B is not in P.

But is it true for NP as well?

If A is not in NP, and A reduces to B, does this mean B is not in NP?

Why or why not?

Thanks!

$\endgroup$
1
$\begingroup$

I'm assuming that both $A$ and $B$ are decision problems and that we are talking bout Karp reductions.

Suppose towards a contradiction that $A \not\in NP$, $A \le_p B$, and $B \in NP$. Then, a non-deterministic polynomial-time Turing machine that decides $A$ would be the following:

  • Use the Karp reduction $f$ from $A$ to $B$ to transform an instance $x$ of $A$ into an instance $f(x)$ of $B$;
  • Simulate a non-deterministic polynomial-time Turing machine $T$ that decides $B$ on input $f(x)$ ($T$ exists since $B \in NP$);
  • If $T(x)$ accepts, accept. If $T(x)$ rejects, reject.

This is a contradiction.

$\endgroup$
1
  • $\begingroup$ Perfect! Thank you! $\endgroup$ – Amy Nov 16 '20 at 13:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.