1. Let X and Y be two decision problems. Suppose we know that X reduces to Y in
ID: 3844747 • Letter: 1
Question
1. Let X and Y be two decision problems. Suppose we know that X reduces to Y in polynomial time. Which of the following can we infer? 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 X is in NP then X is NP-complete. d. If X is NP-complete and Y is in NP then Y is NP-complete. e. X and Y can't both be NP-complete. f. If X is in P, then Y is in P. g. If Y is in P, then X is in P
1. Let X and Y be two decision problems. Suppose we know that X reduces to Y in polynomial time Which of the following can we infer? 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 X is in NP en X is NP-complete. d. f X is NP-complete a Y is in NP en Y is NP-complete. e. X and Y can't both be NP-complete. f. f X is in P, then Y is in P. g. f Y is in P, then X is in PExplanation / Answer
(a) If Y is NP-complete, then so is X
=> False
Since for NP complete. Therefore, X has to be the subset of NP-Complete.
(b) If X is NP-complete, then so is Y
=> False
Here X is NP-Complete and X is polynomial- time reducible to Y. It means time complexity of X is always larger than Y and it can be anything even polynomial.
(c) If Y is NP-complete and X is in NP, then X is NP-complete.
=> False
Since X can be reduced to Y in polynomial time and Y itself is NP-Complete. But it is not possible vice-versa. Thus, it is false.
(d) If X is NP-complete and Y is in NP then Y is NP-complete.
=> True
X can be reduced to Y in polynomial time. Therefore, time complexity of Y is always less than that of X and it can be anything even polynomial.
(e) X and Y can't both be NP-complete.
=> False
X and Y both can be NP-complete only if Y is NP-Complete, X must be NP-Complete.
(f) If X is in P, then Y is in P.
=> False
X is polynomial- time reducible to Y, therefore time complexity of X is always greater than that of Y and X is already a polynomial, Y must also be in polynomial.
(g) If Y is in P, then X is in P.
=> True
X is polynomial- time reducible to Y, therefore time complexity of X is always greater than that of Y and it can be exponential.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.