# NP, NP-Hard and NP-Complete

If a problem S is NP-Complete and we know that a problem Q is polynomial time reducible to S. Does that mean that Q belongs to NP?

Also, when can we state that Q is NP-Hard but does not belong to NP?

If S is polynomial time reducible to R, does that mean R is also NP-Complete? (We do not know if R belongs to NP)

• Please ask only one question per post. If you have multiple questions, you can post them separately, in separate posts.
– D.W.
Apr 9 at 2:13
• Does this answer your question? What is the definition of P, NP, NP-complete and NP-hard? Apr 9 at 8:29
• @D.W. Did not seem logical to put up two separate posts for two basic, single sentenced questions. Would keep that in mind though. Apr 10 at 0:00
• Hey @PålGD! Thanks for the link. Apr 10 at 0:09

If a problem S is NP-Complete and we know that a problem Q is polynomial time reducible to S. Does that mean that Q belongs to NP?

Yes. "$$S$$ is NP-complete" means two things: $$S$$ is NP, and $$S$$ is NP-hard; the second one is irrelevant here, only the first one is needed. Any problem polynomial-time reducible to an NP problem is NP (it works to build the algorithm that first runs the reduction, then runs the non-deterministic algorithm that solves the NP problem).

Also, when can we state that Q is NP-Hard but does not belong to NP?

It suffices to take for $$Q$$ a problem that is "really high" in the complexity hierarchy. For example, take $$Q$$ to be your favorite NEXPTIME-complete problem. By the time hierarchy theorem, we know that NP ⊊ NEXPTIME, so if a problem is NEXPTIME-hard, it cannot be NP (otherwise all NEXPTIME problems could be solved in NP by first reducing to this problem in polytime and then applying the NP algorithm, yielding the absurd NP = NEXPTIME).

If S is polynomial time reducible to R, does that mean R is also NP-Complete? (We do not know if R belongs to NP)

No. It only yields that R is NP-hard, but R may not be in NP. For example, SAT is polytime-reducible to any NEXPTIME-complete problem (because SAT is in NEXPTIME), but such problems are not in NP.

• Thanks. That clears a lot of things! Apr 10 at 0:08