# If A is polynomial time reducible to B and B is in NP, then A is in NP

If $$A\leq_p B$$ and $$B$$ is in $$NP$$, is it true that $$A$$ is in $$NP$$?

What about : "if $$A\leq_p B$$ and $$B$$ is in $$coNP$$, then $$A$$ is in $$coNP$$"?

Thanks in advance.

I think both hold. If $$B$$ is in $$NP$$, then the yes-instances of $$B$$ can be verified in polynomial time. If $$A \leq_p B$$, I can "translate" an instance of $$A$$ to a instance of $$B$$. Then I can use the verification algorithm for $$B$$ to check the yes-instances of $$A$$. The same should be valid for the second affirmation. I'm not sure though.

## 1 Answer

I think both hold too.

Co-NP version:some Problem A reduce to B,

if B is co-NP,$$\overline{B}$$ is in NP,and no-instance of B has some verify way and certificate bit. and A's no-instance can use it too.

So this A is complement of NP problem $$\overline{A}$$. this means complexity class of A is co-NP.

• Thank you for your answer. I don't understand why my post received 2 negative votes. – Pierrot Dec 9 '19 at 13:37
• I don't know that. I did up vote now. – y y Dec 10 '19 at 7:21