Finite Game-of-Life Predecessor Existence is NP-Complete
A machine-supported proof that one-step predecessor existence is NP-complete for explicitly encoded finite Game-of-Life boards with a permanently dead exterior.
- Complexity theory
- Cellular automata
- SAT solving
- Machine-checked artifacts