Consider the following statements:
A. If some NP-complete problem is in P, then P = NP.
B. TSP is in NP.
C. SAT is in NP.
D. The Hamiltonian circuit problem is not NP-complete.
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. A, B and C only
Explanation
A is a standard theorem, and TSP (decision version) and SAT are in NP. The Hamiltonian-circuit problem is NP-complete, so D is false.More Data Structures and Algorithms questions
- A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted into this index, the…
- Suppose a circular queue of capacity n − 1 elements is implemented with an array of n elements. Insertion and deletion use REAR and FRONT a…
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: AVL trees are more balan…
- Consider a hash table of size 7 with starting index 0 and hash function (6x + 3) mod 4. Assuming the table is initially empty, which of the…
- Match List I with List IIList I List II A. Running time of a straightforward recursive method to compute the nth Fibonacci number Fₙ I. O(n…
- Statement I: If f and g are two functions and f = O(g) but g ≠ o(f), we say that the growth rate of g is smaller than that of f. Statement…