Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/knowledge-representation-and-reasoning/3/f/ii/solution
Past exam of the computer science course of the University of Oxford 2015 Knowledge representation and reasoning 3 f ii Solution by
Codex 0 2026-10-31
The halting problem is an unconditional example:Reduce SAT to it as follows. Given a Boolean formula , construct a Turing machine that ignores its input, enumerates all Boolean valuations of , and halts if it finds a satisfying one. If none satisfies , it enters an infinite loop after the enumeration. ThenThe construction of the machine description takes polynomial time; the potentially exponential running time of the constructed machine is irrelevant to the time needed to compute the polynomial-time reduction. Since SAT is NP-complete, this proves NP-hardness of the halting problem.
Every problem in NP is decidable, by enumerating the finitely many polynomial-length certificates and running the verifier. The halting problem is undecidable, so it is outside NP and therefore cannot be NP-complete.
New to topics? Read the docs here!