pith. sign in

arxiv: 2604.24539 · v1 · submitted 2026-04-27 · 💻 cs.LO

The Polynomial Hierarchy and ω-categorical CSPs

Santiago Guzm\'an Pro , Jakub Rydval This is my paper

Pith reviewed 2026-05-07 17:54 UTC · model grok-4.3

classification 💻 cs.LO
keywords categoricalcspsomegalevelbodirskycompletehierarchypolynomial
0
0 comments X

The pith

ω-categorical CSPs are complete for every level of the Polynomial Hierarchy.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Constraint satisfaction problems ask whether variables can be assigned values to satisfy a set of constraints. Some of these problems have a model-theoretic property called ω-categoricity that makes their complexity well-behaved. The Polynomial Hierarchy organizes computational problems by the number of alternating quantifiers needed to solve them. Earlier work found ω-categorical CSPs whose hardness matches specific levels of this hierarchy. The current paper shows such CSPs exist for every level by building them from Monadic Second-Order logic sentences that preserve certain properties under operations, and supplies a new method to produce those sentences.

Core claim

We show that, in fact, there are ω-categorical CSPs complete for any level of the PH.

Load-bearing premise

The recent result of Bodirsky, Knäuer, and Rudolph on constructing ω-categorical CSPs from MSO sentences with preservation properties applies to produce complete problems for every level, and the new tool generates the required sentences.

read the original abstract

In 2008, Bodirsky and Grohe showed that for every $\Pi_n^{\mathrm{P}}$-level of the Polynomial Hierarchy (PH) there are $\omega$-categorical Constraint Satisfaction Problems (CSPs) complete for this level. We show that, in fact, there are $\omega$-categorical CSPs complete for any level of the PH. To this end, we use a recent result of Bodirsky, Kn\"{a}uer, and Rudolph for constructing $\omega$-categorical CSPs from sentences of Monadic Second-Order logic (MSO) with certain preservation properties. As a secondary contribution, we develop a new tool for producing MSO sentences satisfying said preservation properties.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper extends Bodirsky and Grohe (2008) by proving that ω-categorical CSPs exist that are complete for every level of the Polynomial Hierarchy. It does so by invoking the Bodirsky-Knäuer-Rudolph theorem, which converts MSO sentences possessing certain preservation properties into ω-categorical CSP templates, and by supplying a new constructive tool that produces the required MSO sentences for arbitrary PH levels (including Σ_n^P).

Significance. If the new MSO tool is shown to generate sentences whose preservation properties are preserved under the BKR construction and yield the claimed hardness for every PH level, the result would substantially enlarge the known complexity landscape for ω-categorical CSPs. It would demonstrate that such templates can realize the full PH rather than only the co-levels, offering a uniform method for producing hard instances and potentially informing future classification results in algebraic and logical CSP theory.

major comments (1)
  1. The section presenting the new MSO tool: a self-contained argument is needed that the sentences produced satisfy the exact preservation properties required by the BKR theorem and that the induced CSP templates are hard for Σ_n^P (and symmetrically for other levels). This step is load-bearing for the central claim; without an explicit verification that the tool succeeds uniformly across the hierarchy, the extension beyond Bodirsky-Grohe remains unconfirmed.
minor comments (2)
  1. Abstract: the statement that the tool works for 'any level' would benefit from a parenthetical note that both Σ and Π levels are covered.
  2. Notation: ensure that the indexing of PH levels (e.g., Σ_n^P vs. Π_n^P) is introduced consistently before the first use of the BKR construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the correctness of the cited Bodirsky-Knäuer-Rudolph construction theorem for ω-categorical CSPs from MSO sentences with preservation properties and on the effectiveness of the newly developed tool for producing such sentences.

axioms (1)
  • domain assumption MSO sentences with the preservation properties identified by Bodirsky, Knäuer, and Rudolph yield ω-categorical CSPs whose complexity matches the desired PH level
    This is invoked as the basis for constructing the complete CSPs for every level.

pith-pipeline@v0.9.0 · 5407 in / 1199 out tokens · 73088 ms · 2026-05-07T17:54:19.004103+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing

    Libor Barto, Bertalan Bodor, Marcin Kozik, Antoine Mottet, and Michael Pinsker. Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing. In2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–13, 2023

    work page 2023

  2. [2]

    Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures.J

    Libor Barto, Michael Kompatscher, Miroslav Olˇ s´ ak, Van Pham Trung, and Michael Pinsker. Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures.J. Math. Log., 19(02):Article 1950010, 2019

    work page 2019

  3. [3]

    The wonderland of reflections.Isr

    Libor Barto, Jakub Oprˇ sal, and Michael Pinsker. The wonderland of reflections.Isr. J. Math., 223(1):363–398, 2018. 20 SANTIAGO GUZM ´AN-PRO AND JAKUB RYDVAL

    work page 2018

  4. [4]

    Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems).SIAM J

    Libor Barto and Michael Pinsker. Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems).SIAM J. Comput., 49(2):365–393, 2020

    work page 2020

  5. [5]

    Cambridge University Press, 2021

    Manuel Bodirsky.Complexity of infinite-domain constraint satisfaction, volume 52. Cambridge University Press, 2021. Postprint available online

    work page 2021

  6. [6]

    On logics and homomor- phism closure

    Manuel Bodirsky, Thomas Feller, Simon Kn¨ auer, and Sebastian Rudolph. On logics and homomor- phism closure. In2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–13. IEEE, 2021

    work page 2021

  7. [7]

    Non-dichotomies in constraint satisfaction complexity

    Manuel Bodirsky and Martin Grohe. Non-dichotomies in constraint satisfaction complexity. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming - ICALP’08, pages 184–196. Springer, 2008

    work page 2008

  8. [8]

    The complexity of temporal constraint satisfaction problems.J

    Manuel Bodirsky and Jan K´ ara. The complexity of temporal constraint satisfaction problems.J. ACM., 57(2):9:1–9:41, 2010. A conference version appeared in the proceedings of the 40th ACM Symposium on Theory of Computing - STOC’08

    work page 2010

  9. [9]

    Datalog-Expressibility for Monadic and Guarded Second-Order Logic

    Manuel Bodirsky, Simon Kn¨ auer, and Sebastian Rudolph. Datalog-Expressibility for Monadic and Guarded Second-Order Logic. InProceedings of the 48th International Colloquium on Automata, Languages, and Programming - ICALP’21, volume 198 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 120:1–120:17, Dagstuhl, Germany, 2021. Schloss Dagstu...

    work page 2021

  10. [10]

    Constraint satisfaction with countable homogeneous templates

    Manuel Bodirsky and Jaroslav Neˇ setˇ ril. Constraint satisfaction with countable homogeneous templates. J. Log. Comput, 16(3):359–373, 2006. A conference version appeared in the proceedings of Computer Science Logic - CSL’03

    work page 2006

  11. [11]

    Projective clone homomorphisms.J

    Manuel Bodirsky, Michael Pinsker, and Andr´ as Pongr´ acz. Projective clone homomorphisms.J. Symb. Log., 86(1):148–161, 2021

    work page 2021

  12. [12]

    The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems

    Johanna Brunar, Marcin Kozik, Tom´ aˇ s Nagy, and Michael Pinsker. The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems. In2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 403–416, 2025

    work page 2025

  13. [13]

    Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. InProceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science - FOCS’17, pages 319–330. IEEE, 2017

    work page 2017

  14. [14]

    A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. InProceedings of the Ninth Annual ACM Symposium on Theory of Computing, STOC ’77, page 77–90, New York, NY, USA, 1977. Association for Computing Machinery

    work page 1977

  15. [15]

    Existentially restricted quantified constraint satisfaction.Inf

    Hubie Chen. Existentially restricted quantified constraint satisfaction.Inf. Comput., 207(3):369–388, 2009

    work page 2009

  16. [16]

    Tom´ as Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory.SIAM J. Comput., 28(1):57–104, 1998

    work page 1998

  17. [17]

    When symmetries are not enough: A hierarchy of hard constraint satisfaction problems.SIAM J

    Pierre Gillibert, Julius Jonusas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker. When symmetries are not enough: A hierarchy of hard constraint satisfaction problems.SIAM J. Comput., 51(2):175–213, 2022

    work page 2022

  18. [18]

    Cambridge University Press, 1997

    Wilfrid Hodges.A Shorter Model Theory. Cambridge University Press, 1997

    work page 1997

  19. [19]

    On the scope of the universal-algebraic approach to constraint satisfaction.Logical Methods in Computer Science, 8, 2012

    Barnaby Martin, Manuel Bodirsky, and Martin Hils. On the scope of the universal-algebraic approach to constraint satisfaction.Logical Methods in Computer Science, 8, 2012

    work page 2012

  20. [20]

    Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures.J

    Antoine Mottet and Michael Pinsker. Smooth approximations: An algebraic approach to CSPs over finitely bounded homogeneous structures.J. ACM., 71(5):36:1–36:47, 2024

    work page 2024

  21. [21]

    Mark H. Siggers. A strong Mal’cev condition for locally finite varieties omitting the unary type. Algebra Univers., 64:15–20, 2010

    work page 2010

  22. [22]

    A proof of CSP dichotomy conjecture

    Dmitriy Zhuk. A proof of CSP dichotomy conjecture. InProceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science - FOCS’17, pages 331–342. IEEE, 2017

    work page 2017

  23. [23]

    A proof of the CSP dichotomy conjecture.J

    Dmitriy Zhuk. A proof of the CSP dichotomy conjecture.J. ACM., 67(5):30:1–30:78, 2020

    work page 2020

  24. [24]

    QCSP monsters and the demise of the chen conjecture.J

    Dmitriy Zhuk and Barnaby Martin. QCSP monsters and the demise of the chen conjecture.J. ACM, 69(5):35:1–35:44, 2022. Technische Universit ¨at Dresden, Dresden, Germany Email address:santiago.guzman pro@tu-dresden.de Technische Universit ¨at Wien, Vienna, Austria Email address:jakub.rydval@tuwien.ac.at

    work page 2022