Sprague-Grundy theory in bounded arithmetic

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.

References in corpus (1)

• Characterising Complexity Classes by Inductive Definitions in Bounded Arithmetic