= Solution
The <halting problem> is an unconditional example:
$$
\boxed{\mathrm{HALT}\text{ is NP-hard but not NP-complete}.}
$$
Reduce <SAT> to it as follows. Given a <Boolean formula> $\varphi$, construct a <Turing machine> $M_\varphi$ that ignores its input, enumerates all <Boolean valuations> of $\varphi$, and halts if it finds a satisfying one. If none satisfies $\varphi$, it enters an infinite loop after the enumeration. Then
$$
\varphi\in\mathrm{SAT}\quad\Longleftrightarrow\quad\langle M_\varphi,\varepsilon\rangle\in\mathrm{HALT}.
$$
The 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>.
Back to article page
