Given a problem X we want to determine whether X is NP-hard. Therefore,
a. We construct a reduction from instances of problem X to instances of SAT that runs in polynomial time.
b. We construct a reduction from instances of problem X to instances of SAT that runs in polynomial time, such that YES instances of X are mapped to YES instances of SAT, and NO instances of X are mapped to NO instances of SAT.
c. We construct a reduction from SAT to instances of problem X that runs in polynomial time.
d. We construct a reduction from any NP-complete problem (pi) to instances of problem X that run in polynomial time such that YES instances of pi are mapped to YES instances of problem X, and NO instances of pi are mapped to NO instances of X.
e. None of the above
