# If problem A reduces to an NP-Complete problem B, can we say that A is in NP?

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?

## 1 Answer

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$$)