Understanding the Definitions

Exercise 7.2

We have a problem X and we have proved that \mathsf{SAT} reduces to X (formally, \mathsf{SAT} \leq_p X). Which one of the following statements can we derive?

• X belongs to \mathbf{NP}, but we do not know whether it is \mathbf{NP}-complete.
• X is an \mathbf{NP}-complete problem.
• None of the above.

Now, a colleague has additionally found a reduction in the reverse direction, X \leq_p \mathsf{SAT}. What can we conclude now?

• X belongs to \mathbf{NP}, but we do not know whether it is \mathbf{NP}-complete.
• X is an \mathbf{NP}-complete problem.
• None of the above.