Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 11 min ago
PreprintCC BY 4.0arXiv

Exact Complexity of the Satisfiability Problem for Strategy Logic

  • Tikhon Pshenitsyn
Open at sourcePDFDOICite

Abstract

We show that the satisfiability problem for Strategy Logic introduced by Mogavero, Murano, and Vardi is Π1∞-complete, and, more strongly, computably isomorphic to true second-order arithmetic. The lower bound is established for the next-time Boolean-goal fragment of Strategy Logic. Consequently, Strategy Logic is not recursively axiomatizable, even with effectively defined ω-rules.

Related

  1. Monadic second-order logic and the domino problem on self-similar graphs
    Laurent Bartholdi
    Groups, Geometry, and DynamicsPeer-reviewedCC BYFull text3 citedAlgebra & number theoryHAL
  2. On the sample complexity of the generalized hidden shift problem over arbitrary finite groups
    Juntai Zhou
    arXivPreprintarXiv licenceFull textAlgebra & number theoryQuantum physics & quantum informationarXiv
  3. A Uniform Bound on Optimal Strategy Length in Water Transport Problem
    Tianyi Tao, Bohan Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Exact oracle complexity for function-value suboptimality under weighted initial conditions
    Yoel Drori
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Optimal Reinsurance-Dividend Strategy with Fixed Transaction Costs in a Regime-Switching Brownian Risk Model: A Viscosity Solution to the Impulse Control Problem
    Wenyuan Wang, Zuo Quan Xu, Kaixin Yan
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{pshenitsyn2026exact,
  title = {{Exact Complexity of the Satisfiability Problem for Strategy Logic}},
  author = {Tikhon Pshenitsyn},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.16173},
  eprint = {2609.16173},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.16173},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Exact Complexity of the Satisfiability Problem for Strategy Logic
AU  - Tikhon Pshenitsyn
PY  - 2026
DA  - 2026/09/14
PB  - arXiv
DO  - 10.48550/arxiv.2609.16173
UR  - https://arxiv.org/abs/2609.16173
AB  - We show that the satisfiability problem for Strategy Logic introduced by Mogavero, Murano, and Vardi is Π^1_∞-complete, and, more strongly, computably isomorphic to true second-order arithmetic. The lower bound is established for the next-time Boolean-goal fragment of Strategy Logic. Consequently, Strategy Logic is not recursively axiomatizable, even with effectively defined ω-rules.
ER  -