1
$\begingroup$

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)

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks. That clears a lot of things! $\endgroup$ Apr 10 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.