Sprague–Grundy theory in bounded arithmetic

被引：0

作者：

Satoru Kuroda

机构：

[1] Gunma Prefectural Women’s University,

来源：

Archive for Mathematical Logic | 2022年 / 61卷

关键词：

Bounded arithmetic; Combinatorial games; Alternating turing machine; Polynomial space; 03F20;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We will give a two-sort system which axiomatizes winning strategies for the combinatorial game Node Kayles. It is shown that our system captures alternating polynomial time reasonings in the sense that the provably total functions of the theory corresponds to those computable in APTIME. We will also show that our system is equivalently axiomatized by Sprague–Grundy theorem which states that any Node Kayles position is provably equivalent to some NIM heap.

引用

页码：233 / 262

页数：29

共 8 条

[1] Bouton C(1901)NIM, a game with a complete mathematical theory Ann. Math. 3 35-39
[2] Cook SA(1999)Boolean programs and quantified propositional proof systems Bull. Sect. Log. 28 119-129
[3] Soltys M(1939)Mathematics and games Eureka 2 6-8
[4] Grundy PM(1978)On the complexity of some two-person perfect-information games J. Comput. Syst. Sci. 16 185-225
[5] Schaefer TJ(2011)On the complexity of computing winning strategies for finite poset games Theory Comput. Syst. 48 680-692
[6] Soltys M(1935)Tohoku Math. J. Über mathematische Kampfspiele 41 438-444
[7] Wilson C(undefined)undefined undefined undefined undefined-undefined
[8] Sprague RP(undefined)undefined undefined undefined undefined-undefined

← 1 →