PyQdeck LogoPyQdeckSubjects
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

Search GoogleAsk AI

Similar questions

Design and Analysis of Algorithms Compare NP-hard and NP-completeness?20257mDesign & Analysis of AlgorithmsWhat are NP- hard and NP-complete problems?20247mDesign and Analysis of Algorithms What is P, NP, NP hard, and NP complete? Write the relationship between all of them.20237mFORMAL LANGUAGE & AUTOMATA THEORYWrite short notes on: NP-hard and NP-complete problems.20237m
PreviousBFS on a graph G = (V, E) has running time (i) O(|V| + |E|) (ii) O(|V|) (iii) O(|E|) (iv) None of theseNextWhich one of the following functions is asymptotically smallest? (i) 2^n (ii) n^{\log n} (iii) n^{\sqrt{n}} (iv) (100)^{(\log n)^{1/3}} + (\log \log n)^{2/3}