Skip to main content
SpringerLink
Log in

Sprague–Grundy theory in bounded arithmetic

  • Published:
Archive for Mathematical Logic Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bouton, C.: NIM, a game with a complete mathematical theory. Ann. Math. 3, 35–39 (1901)

    Article  MathSciNet  Google Scholar 

  2. Buss, S.R.: Bounded Arithmetic. Ph.D. dissertation, Princeton University (1985)

  3. Cook, S.A., Nguyen, P.: Logical Foundations of Proof Complexity. ASL Perspectives in Logic Series. Cambridge University Press, Cambridge (2010)

    Book  Google Scholar 

  4. Cook, S.A., Soltys, M.: Boolean programs and quantified propositional proof systems. Bull. Sect. Log. 28(3), 119–129 (1999)

    MathSciNet  MATH  Google Scholar 

  5. Eguchi, N.: Characterising Complexity Classes by Inductive Definitions in Bounded Arithmetic. arXiv:1306.5559 [math.LO] (2014)

  6. Grundy, P.M.: Mathematics and games. Eureka 2, 6–8 (1939)

    Google Scholar 

  7. Schaefer, T.J.: On the complexity of some two-person perfect-information games. J. Comput. Syst. Sci. 16(2), 185–225 (1978)

    Article  MathSciNet  Google Scholar 

  8. Siegel, A.N.: Combinatorial Game Theory. Graduate Studies in Mathematics, vol. 146. American Mathematical Society, Providence (2013)

    Book  Google Scholar 

  9. Skelley, A.: Theories and Proof Systems for PSPACE and the EXP-Time Hierarchy. Ph.D. dissertation, University of Toronto (2005)

  10. Soltys, M., Wilson, C.: On the complexity of computing winning strategies for finite poset games. Theory Comput. Syst. 48(3), 680–692 (2011)

    Article  MathSciNet  Google Scholar 

  11. Sprague, R.P.: Tohoku Math. J. Über mathematische Kampfspiele 41, 438–444 (1935)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Gunma Prefectural Women’s University, 1395-1, Kaminote, Tamamura, Gunma, 370-1193, Japan

    Satoru Kuroda

Authors
  1. Satoru Kuroda
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Satoru Kuroda.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The author is grateful to the anonymous referee for invaluable comments.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kuroda, S. Sprague–Grundy theory in bounded arithmetic. Arch. Math. Logic 61, 233–262 (2022). https://doi.org/10.1007/s00153-021-00790-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00153-021-00790-7

Keywords

Mathematics Subject Classification

Search

Navigation