Which of the following is Not a NP Complete problem?
2021
Which of the following is Not a NP Complete problem?
- A.
The Clique problem
- B.
Hamiltonian-Cycle problem
- C.
The Travelling Salesman Problem
- D.
Shortest Path Problem
Attempted by 55 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.