Are the following statements true or false? Why? What could I use to prove these statements?
A decision problem is NP-complete if and only if there is a polynomial-time reduction from SAT to it.
A decision problem is NP-hard if and only if there is a polynomial-time reduction from it to SAT.
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.