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. Whic

Question

3 years ago

12

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. Whic

h 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.

Computers and Technology

1 answer:

tekilochka [14] · Answer 1 · 2022-08-16T03:20:21+03:00

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