Proof of `Arc Kayles is PSPACE-complete` (2nd statement)
groundedproofs/Lax689614Proofs/Completeness.lean · lax-689614
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The compiled depth-first evaluator gives PSPACE membership. Compose positive-CNF PSPACE-hardness with the checked polynomial-time graph reduction to obtain PSPACE-hardness of Arc Kayles.