QUIXO is EXPTIME-complete

DOI10.1016/j.ipl.2020.105995zbMath1462.91007OpenAlexW3038724752MaRDI QIDQ2203590

Shohei Mishiba, Yasuhiko Takenaga

Publication date: 7 October 2020

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2020.105995

zbMATH Keywords

computational complexitygameEXPTIME-completeness

Mathematics Subject Classification ID

2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Cites Work

• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• Computing a perfect strategy for nxn chess requires time exponential in n
• Gobang is PSPACE-complete
• The Othello game on an \(n\times n\) board is PSPACE-complete
• N by N Checkers is Exptime Complete
• Provably Difficult Combinatorial Games