- Author
- Hillel Wayne
- Published
- 16 April 2025
- Kind
- Short newsletter post on computational complexity, with a reader reply
- Original
- buttondown.com/hillelwayne/archive/the-halting-problem-is-a-terrible-example-of-np/
- Subject
- Formal methods and proof
What it is
Hillel Wayne writes the Computer Things newsletter. This post explains NP, NP-hard and NP-complete in brief. It sets out to replace the usual example of a harder-than-NP problem.
What it says
- Wayne says the halting problem is a poor example of a problem harder than NP.
- The post says NP only needs quick checks of yes answers. A halting yes can be checked.
- Wayne says proving halting is outside NP means showing that check grows faster than polynomially.
- Wayne objects most that the example suggests NP-complete is the upper bound of solvable problems.
- Wayne offers a token-on-a-grid reachability problem that is ACKERMANN-complete in the number of dimensions.
- The post calls this problem decidable, easy to explain, and definitely not in NP.
- In a reply, Wayne says solutions can be far longer than the input.
What evidence it gives
The post offers reasoning and definitions, not formal proofs. It describes the grid puzzle in words and points to a friend's Quanta article. One reader asks a question and the author answers it.
Interests and limits
The author calls the post short. The author hedges that the puzzle is PSPACE-complete. The post does not prove its claims about the grid puzzle. The footer promotes the author's book Logic for Programmers.