Let X and Y be two decision problems. Suppose we know that X reduces to Yin polynomial time. Which of the following statements a

Question

2 years ago

14

Let X and Y be two decision problems. Suppose we know that X reduces to Yin polynomial time. Which of the following statements a

re true?Explain
a. If Y is NP-complete then so is X.
b. If X is NP-complete then so is Y.
c. If Y is NP-complete and Xis in NP then X is NP-complete.
d. If X is NP-complete and Y is in NP then Y is NP-complete.
e. If X is in P, then Y is in P.
f. If Y is in P, then X is in P.
g. X and Y can't both be in NP

Computers and Technology

1 answer:

DerKrebs [107] · Answer 1 · 2022-07-14T00:59:31+03:00

Answer:

d. If X is NP - complete and Y is in NP then Y is NP - complete.

This can be inferred

Explanation:

The statement d can be inferred, rest of the statements cannot be inferred. The X is in NP complete and it reduces to Y. Y is in NP and then it is NP complete. The Y is not in NP complete as it cannot reduce to X. The statement d is inferred.