For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time.…
GATE · 2008 · IT
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?
- A.
If X can be solved in polynomial time, then so can Y
- B.
X is NP-complete
- C.
X is NP-hard
- D.
X is in NP, but not necessarily NP-complete
Attempted by 45 students.
Sign up free to check your answer
Sign up freeLoading lesson…