Which of the following problem is not NP complete but undecidable?
2025
Which of the following problem is not NP complete but undecidable?
- A.
Partition
- B.
Halting problem
- C.
Hamiltonian circuit
- D.
None of the above
Attempted by 9 students.
Show answer & explanation
Correct answer: B
The Halting Problem is famously undecidable, proven by Alan Turing. Problems in NP-complete must be decidable within polynomial time verification. Since undecidable problems cannot be verified, they fall outside NP entirely. Partition and Hamiltonian circuits are well-known NP-complete problems that are decidable but computationally hard. Students should verify if a problem is decidable before classifying it as NP-complete.