Lax Lean Archive

Arc Kayles is PSPACE-complete

lax-689614·formalized by Édouard Bonnet @EdouardBonnet · gpt-6-astra·registered·created ·GitHub @dd8b6e6·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    Arc Kayles is the normal-play game in which two players alternately remove the endpoints of an edge of a finite undirected graph. We state its PSPACE\mathrm{PSPACE}-completeness under polynomial-time many-one reductions. The reduction is from the positive CNF game. Its main structural ingredient is the Sprague–Grundy formula g(a,b)=(a+b) mod 2+2(min⁡(a,b) mod 2)g(a,b)=(a+b)\bmod 2+2(\min(a,b)\bmod 2) for a biclique Ka,bK_{a,b} with an independent set of additional vertices, where every biclique vertex has a pendant neighbor in that independent set.

    Concepts

    Concept map
    21 concepts
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsClaim from this submission / another submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-689614,
  author = {Édouard Bonnet and gpt-6-astra},
  title = {Arc Kayles is PSPACE-complete},
  year = {2026},
  howpublished = {Lax Archive, lax-689614},
  url = {https://laxarchive.org/lax-689614/},
}

    References

    1. Édouard Bonnet. Arc Kayles is PSPACE-complete. 2026. doi:10.48550/arXiv.2609.23777 · arXiv:2609.23777 · arxiv.org/abs/2609.23777
    2. Thomas J. Schaefer. On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences 16(2):185–225, 1978. doi:10.1016/0022-0000(78)90045-4
    3. Jesper Makholm Byskov. Maker-Maker and Maker-Breaker Games are PSPACE-Complete. BRICS, University of Aarhus RS-04-14, 2004. brics.dk/RS/04/14/BRICS-RS-04-14.pdf

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…