The Halting Problem is a terrible example of NP-Harder

Original Article ↗ Hacker News Discussion ↗

Halting problem, finite machines, and “fantasy” models

  • Some argue that on a finite-state machine the halting problem is decidable: after at most 2ⁿ steps you either halt or revisit a state and thus loop forever.
  • Others respond this misses the classical halting problem, which assumes unbounded program size and unbounded memory (Turing machines), not fixed finite hardware.
  • It’s noted that physical machines can be modeled with I/O and external storage to approximate “unbounded” memory, and that tracking the full state space is astronomically impractical even if finite.
  • This leads to the broader point: many impossibility results use infinite or asymptotic assumptions, but still map to “no reasonable way to do this” in practice.

Usefulness and limits of Big-O in the real world

  • One subthread debates whether Big-O is “almost useless” for real-world problems because constants and small N dominate.
  • Counterarguments: Big-O is crucial for reasoning about scalability and for insights like hybrid sorts (quicksort + insertion sort) and algorithm choice.
  • Critics emphasize that empirical benchmarks and more detailed cost models (cache, memory layout, constants) are needed beyond pure asymptotics.

NP, NP-hard, NP-complete, and beyond

  • Several comments clarify:
    • NP-complete = NP ∩ NP-hard.
    • NP-hard problems may lie outside NP (e.g., not polynomially verifiable).
    • Membership in NP is about ease of verification, NP-hardness about difficulty of solving.
  • There’s discussion of HALT as RE-complete and “bigger” than NP, and of the time hierarchy theorem and polynomial hierarchy as more precise frameworks than just invoking halting.

Vector Addition Systems / Diophantine reachability as “NP-harder”

  • The article’s grid/jump problem is identified as Vector Addition System (VAS) reachability, equivalent to Petri nets.
  • Key property: shortest witnesses can be Ackermann-scale long, far beyond any polynomial in input size, so even verifying a “path” certificate is not polynomial in the original input. Hence it’s decidable and NP-hard but not in NP.
  • Some readers struggle with decision vs search formulations and with separating “long outputs” from genuine super-polynomial verification cost.

Approximate halting and practical complexity

  • A side discussion covers partial “halting oracles” (time-bounded or problem-restricted analyses), genetic programming with cutoffs, and heuristic solvers.
  • Consensus: such methods don’t evade the fundamental theorems; they exploit that many real instances are easy while the worst cases remain intractable.