0
$\begingroup$

I was reviewing All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

I understand that the general way we show a problem A is in NP is to show there exists a poly-time certifier for A. However, I am confused if say, we know nothing about A, and it reduces to an NP-Complete problem B, can we now say that A is in NP?

I understand that all problems in NP reduce to any NP-Complete problems, but I'm not sure if this will prove anything. I also understand to show a problem is NP-Complete, we first show it's in NP with a poly-time verifier/certificate and then reduce an NP-Complete problem to it. But confused about this other scenario:

Let A be an unknown problem. Let B be a known problem in NP-Complete. A reduces to B What does this tell us about A?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes (assuming you meant poly-time reductions).

Being in $NP-complete$ is equivalent to being in both classes:

  1. NP
  2. NP-hard

In particular, $B\in NP$. Now, $A\in NP$ since $A\le_p B$ and $NP$ is closed under poly-time reductions (you can easily see how to create a non-deterministic poly-time TM for $A$ given the reduction $f$ and a TM for $B$)

$\endgroup$

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.