Which of the following is Not a NP Complete problem?
2021
Which of the following is Not a NP Complete problem?
Answer: D. Shortest Path Problem — The Shortest Path Problem can be solved in polynomial time using algorithms like Dijkstra's, placing it in class P rather than NP Complete. In contrast,…
- A.
The Clique problem
- B.
Hamiltonian-Cycle problem
- C.
The Travelling Salesman Problem
- D.
Shortest Path Problem
Attempted by 194 students.
Show answer & explanation
Correct answer: D
The Shortest Path Problem can be solved in polynomial time using algorithms like Dijkstra's, placing it in class P rather than NP Complete. In contrast, problems such as the Clique problem and Hamiltonian-Cycle are proven to be NP Complete because no polynomial-time solution is known.
Loading lesson…