GATE 2021 CS-Set-2
October 12, 2023
Artificial-intelligence
October 12, 2023
GATE 2021 CS-Set-2
October 12, 2023
Artificial-intelligence
October 12, 2023

GATE 2008-IT

Question 11

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
Question 11 Explanation: 
Note: Out of syllabus.
Correct Answer: D
Question 11 Explanation: 
Note: Out of syllabus.

Leave a Reply

Your email address will not be published. Required fields are marked *