PreprintarXiv licencearXiv
Arc Kayles is PSPACE-complete
Abstract
We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1976.
Related
- The Two-Level Poset Game is PSPACE-Complete
- PL Recognition After Two S2× S2 Stabilisations is PSPACE-Hard
- One Polynomial Field for Every Euler Step and the Flow: Polynomial Dynamics for P and PSPACE
- A Complete Solution to the Conjecture on the Inverse Collatz–Sinogowitz Irregularity Problem
- Extension of valuation rings as limits of complete intersection algebras
BibTeX
@misc{bonnet2026kayles,
title = {{Arc Kayles is PSPACE-complete}},
author = {Édouard Bonnet},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.23777},
eprint = {2609.23777},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23777},
}
RIS
TY - UNPB
TI - Arc Kayles is PSPACE-complete
AU - Édouard Bonnet
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2609.23777
UR - https://arxiv.org/abs/2609.23777
AB - We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1976.
ER -