Gate CS-2006 Question Paper With Solutions

Q. 75 Let S be an NP-complete problem 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?

(A) R is NP-complete

(B) R is NP-hard

(C) Q is NP-complete

(D) Q is NP-hard

Answer: (B)

Explanation: Gate CS-2006 Question Paper With Solutions

Learn More:   Gate EC-2015 - 1 Question Paper With Solutions

LEAVE A REPLY

Please enter your comment!
Please enter your name here