0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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.