Which of the following problem is not NP complete but undecidable?

2025

Which of the following problem is not NP complete but undecidable?

  1. A.

    Partition

  2. B.

    Halting problem

  3. C.

    Hamiltonian circuit

  4. 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.

Explore the full course: Mppsc Assistant Professor