Arc Kayles game complexity is proven PSPACE-complete
Arc Kayles is PSPACE-complete
Computational ComplexityDiscrete Mathematics
Summary
The difficulty of solving the game Arc Kayles has been proven to be very high, specifically PSPACE-complete. This means that determining the winner or the best moves in this game is as hard as the toughest problems that can be solved with a reasonable amount of memory but possibly a very long time. The authors resolved a long-standing question from 1978 posed by Schaefer about how complex this game really is. This proof helps us understand which game problems are computationally hard.
What this means in practice
- •For game algorithm designers: Avoid attempts to find efficient winning strategies for Arc Kayles due to its PSPACE-completeness.
- •For complexity theorists: Use the PSPACE-completeness of Arc Kayles to benchmark other game problems and computational models.
A theory result. No direct application yet.
Authors
Édouard Bonnet
Abstract
We show that Arc Kayles is PSPACE-complete. This solves a question raised by Schaefer in 1978.