pith. sign in

arxiv: 2605.09815 · v1 · submitted 2026-05-10 · 💻 cs.CC

Towards infinite PCSP: a dichotomy for monochromatic cliques

Demian Banakh , Alexey Barsukov , Tamio-Vesa Nakajima This is my paper

Pith reviewed 2026-05-12 02:00 UTC · model grok-4.3

classification 💻 cs.CC
keywords PMMSNPPromise CSPmonochromatic cliquesRich 2-to-1 Conjecturehypergraph coloringreconfigurabilitydichotomyMMSNP
0
0 comments X

The pith

Every PMMSNP problem reduces in polynomial time to a finite-domain Promise CSP, with a full complexity classification for the monochromatic-clique subclass assuming the Rich 2-to-1 Conjecture.

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

The paper defines Promise MMSNP as a promise analogue of the MMSNP logic that captures finite-domain CSPs. It proves that every problem in this new class is polynomial-time equivalent to a Promise CSP over a finite domain, extending the classical correspondence. For the subclass of problems that forbid monochromatic cliques, including many promise graph-coloring tasks, the authors obtain a complete dichotomy between polynomial-time solvable and NP-hard cases, but only if the Rich 2-to-1 Conjecture holds. A key technical step is an NP-hardness proof for properly coloring uniform hypergraphs that are promised to admit a reconfigurable coloring, again conditional on the conjecture. This hardness result also implies most cases of the linearly-ordered colouring conjecture.

Core claim

The authors show that Promise MMSNP problems are polynomial-time equivalent to finite-domain Promise CSPs. For the monochromatic-clique class they give a full complexity classification conditional on the Rich 2-to-1 Conjecture, proving that the problems are either in P or NP-hard. The classification relies on an intermediate NP-hardness result for reconfigurable uniform hypergraph coloring under the same conjecture.

What carries the argument

The polynomial-time reduction from PMMSNP to finite-domain PCSP, together with the reconfigurability promise on hypergraph colorings that enables the hardness proof under the Rich 2-to-1 Conjecture.

If this is right

  • Every PMMSNP problem is polynomial-time equivalent to a finite-domain PCSP.
  • Monochromatic-clique PMMSNP problems are either in P or NP-hard, assuming the Rich 2-to-1 Conjecture.
  • Coloring a uniform hypergraph is NP-hard even when a reconfigurable coloring is promised to exist, under the Rich 2-to-1 Conjecture.
  • Most instances of the linearly-ordered colouring conjecture follow from the reconfigurable-hypergraph hardness result.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique may apply to other promise logics beyond MMSNP.
  • If the Rich 2-to-1 Conjecture is eventually proved, the paper would resolve the complexity status of many open promise-coloring problems.
  • The reconfigurability condition could serve as a reusable gadget in hardness proofs for other infinite-domain promise problems.

Load-bearing premise

The Rich 2-to-1 Conjecture holds, which supplies the NP-hardness of reconfigurable hypergraph coloring.

What would settle it

A polynomial-time algorithm that properly colors any uniform hypergraph promised to admit a reconfigurable coloring, or an explicit counterexample to the Rich 2-to-1 Conjecture.

read the original abstract

The logic MMSNP is a well-studied fragment of Existential Second-Order logic that, from a computational perspective, captures finite-domain Constraint Satisfaction Problems (CSPs) modulo polynomial-time reductions. At the same time, MMSNP contains many problems that are expressible as $\omega$-categorical CSPs but not as finite-domain ones. We initiate the study of Promise MMSNP (PMMSNP), a promise analogue of MMSNP. We show that every PMMSNP problem is poly-time equivalent to a (finite-domain) Promise CSP (PCSP), thereby extending the classical MMSNP-CSP correspondence to the promise setting. We then investigate the complexity of PMMSNPs arising from forbidding monochromatic cliques, a class encompassing promise graph colouring problems. For this class, we obtain a full complexity classification conditional on the Rich 2-to-1 Conjecture, a recently proposed perfect-completeness surrogate of the Unique Games Conjecture. As a key intermediate step which may be of independent interest, we prove that it is NP-hard, under the Rich 2-to-1 Conjecture, to properly colour a uniform hypergraph even if it is promised to admit a colouring satisfying a certain technical condition called reconfigurability. This proof is an extension of the recent work of Braverman, Khot, Lifshitz and Minzer (Adv. Math. 2025). To illustrate the broad applicability of this theorem, we show that it implies most of the linearly-ordered colouring conjecture of Barto, Battistelli, and Berg (STACS 2021).

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 introduces Promise MMSNP (PMMSNP) as a promise analogue of MMSNP and proves that every PMMSNP problem is polynomial-time equivalent to a finite-domain Promise CSP (PCSP). It then establishes a complexity dichotomy for the monochromatic-clique subclass of PMMSNP (encompassing promise graph colouring) conditional on the Rich 2-to-1 Conjecture. As an intermediate step, it proves NP-hardness of properly colouring uniform hypergraphs under a reconfigurability promise (extending Braverman et al. 2025) and shows this implies most of the linearly-ordered colouring conjecture of Barto et al. (STACS 2021).

Significance. If the results hold, the work extends the classical MMSNP-CSP correspondence to the promise setting, providing a concrete link between logic-based promise problems and finite-domain PCSPs. The conditional dichotomy for monochromatic cliques offers a classification for an important class including promise colourings, while the reconfigurability hardness result has independent interest and applies to other open problems. The use of the Rich 2-to-1 Conjecture as a perfect-completeness surrogate is a strength, as is the explicit separation of unconditional and conditional parts.

major comments (1)
  1. The key hardness result for reconfigurable uniform hypergraph colouring (abstract and main body) is described as an extension of Braverman, Khot, Lifshitz and Minzer (Adv. Math. 2025). The manuscript provides only a high-level sketch of how the extension is obtained; this is load-bearing for the conditional dichotomy and requires a self-contained argument or detailed reference to the modified steps to allow verification.
minor comments (2)
  1. The term 'reconfigurability' is used in the abstract without a one-sentence definition or pointer to its formal definition in the paper; adding this would improve readability for readers unfamiliar with the technical condition.
  2. The introduction should include a short paragraph explicitly separating the unconditional equivalence result from the conditional dichotomy to prevent any misreading of the scope.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, positive summary, and constructive feedback. We address the single major comment below and will revise the manuscript to incorporate the requested details.

read point-by-point responses

  1. Referee: The key hardness result for reconfigurable uniform hypergraph colouring (abstract and main body) is described as an extension of Braverman, Khot, Lifshitz and Minzer (Adv. Math. 2025). The manuscript provides only a high-level sketch of how the extension is obtained; this is load-bearing for the conditional dichotomy and requires a self-contained argument or detailed reference to the modified steps to allow verification.

    Authors: We agree that the current presentation of the reconfigurable hypergraph colouring hardness result (which underpins the conditional dichotomy for monochromatic-clique PMMSNP) consists of a high-level sketch of the modifications to the Braverman et al. argument. In the revised manuscript we will replace this sketch with a self-contained, detailed proof that explicitly identifies each modified step, the new technical ingredients required for the reconfigurability promise, and the points at which the Rich 2-to-1 Conjecture is invoked. This will enable independent verification without requiring the reader to reconstruct the extension from the original paper. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's core claims—an unconditional polynomial-time equivalence between every PMMSNP problem and a finite-domain PCSP, plus a conditional dichotomy for the monochromatic-clique subclass—are derived from external assumptions (the Rich 2-to-1 Conjecture) and extensions of independent prior results by other authors (Braverman-Khot-Lifshitz-Minzer and Barto-Battistelli-Berg). No equations, definitions, or steps reduce the claimed results to self-citations, fitted parameters, or inputs by construction. The argument structure remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the Rich 2-to-1 Conjecture as an external assumption; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption Rich 2-to-1 Conjecture
    Invoked to prove NP-hardness of reconfigurable hypergraph coloring and to obtain the full dichotomy.

pith-pipeline@v0.9.0 · 5590 in / 1152 out tokens · 53291 ms · 2026-05-12T02:00:39.417133+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

21 extracted references · 21 canonical work pages

  1. [1]

    Improved Inapproximability of Rainbow Coloring

    1 Per Austrin, Amey Bhangale, and Aditya Potukuchi. Improved Inapproximability of Rainbow Coloring. In Shuchi Chawla, editor,Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), page 1479–1495. SIAM, January 2020.arXiv:1810.02784, doi:10.1137/1.9781611975994.90. 2 Per Austrin, Johan Håstad, and Björn Martinsson. On the Usefulness of P...

    work page doi:10.1137/1.9781611975994.90 2020

  2. [2]

    Containment for Guarded Monotone Strict NP

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.140. 7 Libor Barto, Diego Battistelli, and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 ofLeibniz International Proceedings in Inf...

    work page doi:10.4230/lipics.icalp.2025.140 2025

  3. [3]

    8 Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal

    Schloss Dagstuhl – Leibniz- Zentrum für Informatik.doi:10.4230/LIPIcs.STACS.2021.10. 8 Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. Algebraic Approach to Promise Constraint Satisfaction.Journal of the ACM, 68(4), July 2021.doi:10.1145/3457606. 9 Meghyn Bienvenu, Balder Ten Cate, Carsten Lutz, and Frank Wolter. Ontology-Based Data Access: A ...

    work page doi:10.4230/lipics.stacs.2021.10 2021

  4. [4]

    12 Manuel Bodirsky and Jan Kára

    Springer Berlin Heidelberg.doi:10.1007/978-3-540-70583-3_16. 12 Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. J. ACM, 57(2):9:1–9:41, January 2010.doi:10.1145/1667053.1667058. 13 Manuel Bodirsky, Simon Knäuer, and Florian Starke. ASNP: a tame fragment of existential second-order logic. InBeyond the horizon of c...

    work page doi:10.1007/978-3-540-70583-3_16 2010

  5. [5]

    Madelaine, and Antoine Mottet

    doi: 10.1137/19M128466X. 24 Towards infinite PCSP: a dichotomy for monochromatic cliques 16 Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint satisfaction problems for reducts of homogeneous graphs.SIAM J. Comput., 48(4):1224–1264, 2019.doi:10.1137/16M1082974. 17 Manuel Bodirsky, Michael Pinsker, and András Pongrácz. Projec...

    work page doi:10.1137/19m128466x 2019

  6. [6]

    20 Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep

    doi: 10.1145/3459668. 20 Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. Conditional Dichotomy of Boolean Ordered Promise CSPs.TheoretiCS, 2, January 2023.doi:10.46298/theoretics. 23.2. 21 Alex Brandts and Stanislav Živný. Beyond PCSP(1-in-3, NAE).Inform. and Comput., 289, November 2022.doi:10.1016/j.ic.2022.104954. 22 Mark Braverman, Subhash Kh...

    work page doi:10.1145/3459668 2023

  7. [7]

    23 Mark Braverman, Subhash Khot, and Dor Minzer

    doi: 10.1016/j.aim.2025.110460. 23 Mark Braverman, Subhash Khot, and Dor Minzer. On Rich 2-to-1 Games. In12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:20, Dagstuhl, Germany,

    work page doi:10.1016/j.aim.2025.110460 2025

  8. [8]

    On Rich 2-to-1 Games , booktitle =

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.ITCS.2021.27. 24 Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of con- straints using finite algebras.SIAM J. Comput., 34(3):720–742,

    work page doi:10.4230/lipics.itcs.2021.27 2021

  9. [9]

    [BˇZ20] Silvia Butti and Stanislav ˇZivn´ y

    doi:10.1137/ S0097539700376676. 25 Andrei A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In Chris Umans, editor, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), page 319–330. IEEE, October 2017.doi:10.1109/FOCS.2017.37. 26 Stefan A. Burr. On the computational complexity of Ramsey-type problems. InMathematics of Ramsey theo...

    work page doi:10.1109/focs.2017.37 2017

  10. [10]

    27 Maria Chudnovsky, Linda Cook, James Davies, and Sang-il Oum

    doi: 10.1007/978-3-642-72905-8_5. 27 Maria Chudnovsky, Linda Cook, James Davies, and Sang-il Oum. Reuniting𝜒-boundedness with polynomial 𝜒-boundedness.J. Combin. Theory Ser. B, 176:30–73, 2026.doi:10.1016/j. jctb.2025.08.002. 28 Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin, Tamio-Vesa Nakajima, and Stanislav Živný. 1-in-3 vs. not-all-equal: Dichotomy of a...

    work page doi:10.1007/978-3-642-72905-8_5 2026

  11. [11]

    33 Tomás 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.doi:10.1137/S0097539794266766. 34 Miron Ficak, Marcin Kozik, Miroslav Olšák, and Szymon Stankiewicz. Dichotomy for Sym- metric Boolean PCSPs. In46th International C...

    work page doi:10.1137/s0097539794266766 1998

  12. [12]

    35 Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.ICALP.2019.57. 35 Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs.ACM Trans. Comput. Theory, 18(2), May 2026.doi:10.1145/3779121. 36 Michael R. Garey and David S. Johnso...

    work page doi:10.4230/lipics.icalp.2019.57 2019

  13. [13]

    37 Venkatesan Guruswami and Euiwoong Lee

    A guide to the theory of NP-completeness. 37 Venkatesan Guruswami and Euiwoong Lee. Strong inapproximability results on bal- anced rainbow-colorable hypergraphs.Combinatorica, 38(3):547–599, 2018.doi:10.1007/ s00493-016-3383-0. 38 Venkatesan Guruswami and Rishi Saket. Hardness of Rainbow Coloring Hypergraphs. In Satya V. Lokam and R. Ramanujam, editors,37...

    work page 2018

  14. [14]

    39 Venkatesan Guruswami and Sai Sandeep

    Schloss Dagstuhl - Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.FSTTCS.2017.33. 39 Venkatesan Guruswami and Sai Sandeep. d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors. In47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 62...

    work page doi:10.4230/lipics.fsttcs.2017.33 2017

  15. [15]

    doi:10.4230/LIPIcs.ICALP.2020.62

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2020.62. 40Wilfrid Hodges.A shorter model theory. Cambridge University Press,

    work page doi:10.4230/lipics.icalp.2020.62 2020

  16. [16]

    42 Michał Karpiński and Krzysztof Piecuch

    doi:10.1137/0208040. 42 Michał Karpiński and Krzysztof Piecuch. On vertex coloring without monochromatic triangles. InComputer science—theory and applications, volume 10846 ofLecture Notes in Comput. Sci., pages 220–231. Springer, Cham, 2018.doi:10.1007/978-3-319-90530-3_19. 43 Subhash Khot. On the power of unique 2-prover 1-round games. InProceedings of ...

    work page doi:10.1137/0208040 2018

  17. [17]

    co.uk/downloads/ifcolog00028.pdf,arXiv:1603.00082

    URL:https://www.collegepublications. co.uk/downloads/ifcolog00028.pdf,arXiv:1603.00082. 47 Andrei Krokhin and Danny Vagnozzi. Approximating 1-in-3 SAT by linearly ordered hyper- graph 3-colouring is NP-hard, 2025.arXiv:2508.14606,doi:10.48550/arXiv.2508.14606. 48 Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, and Stanislav Živný. Topology and Adjunction...

    work page doi:10.48550/arxiv.2508.14606 2025

  18. [18]

    52 Florent Madelaine and Iain A. Stewart. Constraint satisfaction, logic and forbidden patterns. SIAM J. Comput., 37(1):132–163, January 2007.doi:10.1137/050634840. 53 Sebastian Meyer and Jakub Opršal. A topological proof of the Hell-Nešetřil dichotomy. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Disc...

    work page doi:10.1137/050634840 2007

  19. [19]

    Linearly Ordered Colourings of Hypergraphs , journal =

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/ LIPIcs.ICALP.2025.169. 57 Tamio-Vesa Nakajima and Stanislav Živný. Linearly ordered colourings of hypergraphs.ACM Trans. Comput. Theory, 14(3–4), February 2023.doi:10.1145/3570909. 58 Omer Reingold. Undirected connectivity in log-space.J. ACM, 55(4), September

    work page doi:10.1145/3570909 2025

  20. [20]

    59 Sai Sandeep

    doi:10.1145/1391289.1391291. 59 Sai Sandeep. Almost optimal inapproximability of multidimensional packing problems. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 245–256. IEEE, 2021.arXiv:2101.02854,doi:10.1109/FOCS52979.2021.00033. 60 Dmitriy Zhuk. A Proof of CSP Dichotomy Conjecture. In Chris Umans, editor,2017 IEEE...

    work page doi:10.1145/1391289.1391291 2021

  21. [21]

    A Proof of the CSP Dichotomy Conjecture

    doi:10.1145/3402029. A Noise inequalities Correlation plays an important role in our analysis. For a distributionΩ over 𝐴×𝐵 , it is denoted by 𝜌(𝐴, 𝐵 ; Ω) ∈ [ 0, 1]. We will not define it formally here; the intuition behind 𝜌(𝐴, 𝐵 ; Ω) is that it measures the correlation between the first and second coordinates ofΩ. The reason BKLM-connected relations are...

    work page doi:10.1145/3402029