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

💬 Discuss

✅ Correct Answer: (A) R is NP-complete

Published by Mr. Dubey ⭐ 111.54K Points at 18-Sep-2023 04:33 pm in Theory of Computation

You must be Logged in to update hint/solution

💬 Discussion

📊 Question Analytics

👁️

148

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

87%

Success Rate