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!
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI 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!
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:
This is a contradiction.