Question 5485 – NIELIT Junior Teachnical Assistant_2016_march
February 23, 2024Question 9669 – GATE 2002
February 24, 2024Question 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