###### Question 5485 – NIELIT Junior Teachnical Assistant_2016_march

February 23, 2024###### Question 9669 – GATE 2002

February 24, 2024# Question 9329 – P-NP

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?

Correct Answer: B

Question 7 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.

R is NP-complete

R is NP-hard

Q is NP-complete

Q is NP-hard

Subscribe

Login

0 Comments