Question

Consider two decision problems X and Y. If X reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Y. Which of the following can be inferred from the previous statement?

a. X is in NP and Y is in NP-Hard.
b. Y is in NP and X is in NP-Hard.
c. Both X and Y are in NP-hard.
d. Both X and Y are in NP.

Answer 1

Answer:

X is in NP and Y is in NP-HARD ( A )

Explanation:

X is in NP and Y is in NP-HARD can be inferred from the previous statement made in the problem above because  problem decision X  can be in NP if it can BE reducible to a 3-SAT polynomial real time, if that can be achieved then  3SAT will be in NP since SAT is in NP as well.

also problem decision Y  can be in NP-HARD if 3SAT can be reducible to it in polynomial time as well hence option A is the correct option