A. If some NP-complete problem P is in π«, then π« = π©π«. B. TSP is in π©π«. C. SAT is in π©π«. D. The Hamiltonian circuit problem is not NP-complete. Which are correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. A, B and C only
Explanation
A polynomial algorithm for one NP-complete problem solves all of NP. The decision versions of TSP and SAT are in NP. The Hamiltonian circuit problem is NP-complete, so D is false.
More Data Structures and Algorithms questions
- Suppose a circular queue of capacity n-1 elements is implemented with an array of n elements. Assume that the insertion and deletion operatβ¦
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: The AVL trees are more bβ¦
- Consider a hash table of size seven with starting (6x + 3) mod 4 index zero and a hash function . Assuming the hash table is initially emptβ¦
- Match List I with List II
- Given below are two statements: Statement I: If f and g are two functions and f = O(g) g β o(f) but , we say that the growth rate of g is sβ¦
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: It is possible to createβ¦