Back to the 2022 paper

Module 4: Tractable and Intractable Problems

20222m

Which one is true of the following
(i) all NP hard problems are NP complete
(ii) all NP complete problems are NP hard
(iii) some NP complete problems are NP hard
(iv) None of these

Worked SolutionAI Assisted

Answer: (ii) all NP complete are NP hard

NP-complete = NP ∩ NP-hard. All NP-complete are NP-hard and in NP; not all NP-hard are NP-complete (some not in NP). So (ii) true, (i) false.

Similar questions

Student FinanceWeb Platform

Pocketly — Personal Finance for Students

Keep your hostel and college expenses under control. Track accounts, log spending in seconds, and stay within your monthly budget.