GATE 2006
|
Question 16
|
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
|
R is NP-complete
|
|
|
R is NP-hard
|
|
|
Q is NP-complete
|
|
|
Q is NP-hard
|
Question 16 Explanation:
NP-Hard- if it can be solved in polynomial time then all NP-Complete can be solved in polynomial time. If NP Hard problem is reducible to another problem in Polynomial Time, then that problem is also NP Hard which means every NP problem can be reduced to this problem in Polynomial Time.
Correct Answer: B
Question 16 Explanation:
NP-Hard- if it can be solved in polynomial time then all NP-Complete can be solved in polynomial time. If NP Hard problem is reducible to another problem in Polynomial Time, then that problem is also NP Hard which means every NP problem can be reduced to this problem in Polynomial Time.