0

Are the following statements true or false? Why? What could I use to prove these statements?

  1. A decision problem is NP-complete if and only if there is a polynomial-time reduction from SAT to it.

  2. A decision problem is NP-hard if and only if there is a polynomial-time reduction from it to SAT.

John
  • 1

1 Answers1

2

Note that SAT is an NP-hard problem, meaning for any problem X in NP, there is a polynomial-time reduction from X to SAT. If there is a p-time reduction from SAT to Y, then by transitivity, any problem in NP has a p-time reduction to Y, hence Y must be NP-hard. But we do not know if it is in NP or not, hence we cannot deduce that it is NP-complete. It could be a problem that is much higher in the hierarchy. So the first item is false. On the other hand, if there is a p-time reduction from X to SAT, then X must be in NP, since SAT itself is in NP. But is it NP-hard? Not necessarily, X could be in P, for example. So the second item is also false.

Levent
  • 4,804
  • You are right, I used the term "reduction from SAT to X" backwards and I fix it now. – Levent Apr 25 '21 at 14:57
  • It doesn't affect the final answer, but in the second case the implication that X is in NP depends on whether we're talking about Karp or Cook reductions. – Especially Lime Apr 30 '21 at 14:02