Choose the correct statement(s)
A. A problem which is NP-Complete will have the property that it can be solved in polynomial time iff all other NP-complete problems can also be solved in polynomial time.
B. All NP-complete problems are NP-hard problems.
C. If an NP-hard problem can be solved in polynomial time, then all NP-complete problems can be solved in polynomial time.
D. All NP-hard problems are 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: D. A, B, C, D
Explanation
All NP-complete problems reduce to one another in polynomial time (A). NP-complete = NP ∩ NP-hard (B). Every NP problem reduces to an NP-hard problem, so a polynomial algorithm for it solves all NP-complete problems (C). D means 'not every NP-hard problem is NP-complete' (e.g. the halting problem), which is true.More Data Structures and Algorithms questions
- Consider the binary tree: A is the root with left child B and right child C; C has left child D and right child E; E has right child F; F h…
- Which of the following uses only increment operations for adding and removing elements at either end?
- Match List I with List IIList I List II A. Breadth First Search I. LISP B. Depth First Search II. Syntax tree C. Prefix III. Stack D. Infix…
- Which of the following is NOT a divide and conquer method?
- Arrange the following steps of the inorder traversal of a binary tree in the correct order. A. Visit the left subtree B. Visit the root nod…
- Which of the following algorithms are based on Breadth First Search (BFS)? A. Prim's algorithm B. Kruskal's algorithm C. Dijkstra's algorit…