Sprague-Grundy theory in bounded arithmetic

2016/09/08 by Satoru Kuroda, Kuroda, Satoru
Mathematics · #FOS: Mathematics #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.1609.02408

arxiv created 2016/09/08 · arxiv updated 2016/09/09

Abstract

In this paper, we formalize Sprague-Grundy theory for combinatorial games in bounded arithmetic. We show that in the presence of Sprague-Grundy numbers, a fairly weak axioms capture PSPACE.

Related

• Two Games on Arithmetic Functions: SALIQUANT and NONTOTIENT
• Game Values of Arithmetic Functions
• The Sprague-Grundy function for some selective compound games
• Extended Sprague-Grundy Theory for Locally Finite Games, and Applications to Random Game-trees
• Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings