pith. sign in

arxiv: 2602.00778 · v2 · submitted 2026-01-31 · 💻 cs.CC · math.RA

The complexity of finding coset-generating polymorphisms and the promise metaproblem

Manuel Bodirsky , Armin Wei{\ss} This is my paper

Pith reviewed 2026-05-16 08:53 UTC · model grok-4.3

classification 💻 cs.CC math.RA
keywords polymorphismmetaproblemcoset-generatingheapNP-completenesspromise constraint satisfactionMaltsev polymorphism
0
0 comments X

The pith

The metaproblem for coset-generating polymorphisms is NP-complete.

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

The paper proves that, given a finite structure, deciding whether it admits a polymorphism of the form (x,y,z) maps to x y inverse z for some group is NP-complete. This settles an open question of Chen and Larose. The work also defines a promise version of the metaproblem parameterized by two polymorphism conditions and supplies sufficient criteria for the promise version to lie in P or to be NP-hard. One highlighted case places the promise problem in P even though the corresponding unconditional metaproblems remain open.

Core claim

The metaproblem asking whether a finite structure possesses a coset-generating polymorphism (equivalently, a heap polymorphism xy inverse z with respect to some group) is NP-complete. The promise metaproblem for a pair of conditions Sigma1 and Sigma2 is in P when Sigma1 requires a Maltsev polymorphism and Sigma2 requires an abelian heap polymorphism. The creation-metaproblem for Maltsev polymorphisms under the promise that a heap polymorphism exists is in P if and only if there exists a uniform polynomial-time algorithm for CSPs admitting heap polymorphisms.

What carries the argument

The metaproblem (and its promise variant) that takes a finite structure and asks whether it admits a polymorphism satisfying a given algebraic condition Sigma.

If this is right

  • The open question of Chen and Larose receives an NP-completeness answer.
  • The promise metaproblem combining a Maltsev condition with an abelian-heap condition is solvable in polynomial time.
  • The creation-metaproblem for Maltsev polymorphisms under a heap promise is in P precisely when a uniform polynomial-time algorithm exists for all heap-CSP instances.

Where Pith is reading between the lines

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

  • Promise restrictions can render algebraic decision problems tractable even when the corresponding unconditional problems stay open.
  • The equivalence between the creation-metaproblem and uniform CSP algorithms suggests a route to classifying tractable CSP classes via promise metaproblems.
  • Similar promise techniques may apply to other open metaproblems in the study of polymorphisms and constraint satisfaction.

Load-bearing premise

The reduction establishing NP-completeness relies on the standard encoding of input structures and the usual definition of group operations over finite domains.

What would settle it

A polynomial-time algorithm that decides, for every finite structure, whether a coset-generating polymorphism exists would falsify the NP-completeness claim.

read the original abstract

We show that the metaproblem for coset-generating polymorphisms is NP-complete, answering a question of Chen and Larose: given a finite structure, the computational question is whether this structure has a polymorphism of the form $(x,y,z) \mapsto x y^{-1} z$ with respect to some group; such operations are also called coset-generating, or heaps. Furthermore, we introduce a promise version of the metaproblem, parametrised by two polymorphism conditions $\Sigma_1$ and $\Sigma_2$ and defined analogously to the promise constraint satisfaction problem. We give sufficient conditions under which the promise metaproblem for $(\Sigma_1,\Sigma_2)$ is in P and under which it is NP-hard. In particular, the promise metaproblem is in P if $\Sigma_1$ states the existence of a Maltsev polymorphism and $\Sigma_2$ states the existence of an abelian heap polymorphism -- despite the fact that neither the metaproblem for $\Sigma_1$ nor the metaproblem for $\Sigma_2$ is known to be in P. We also show that the creation-metaproblem for Maltsev polymorphisms, under the promise that a heap polymorphism exists, is in P if and only if there is a uniform polynomial-time algorithm for CSPs with a heap polymorphism.

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

0 major / 3 minor

Summary. The manuscript proves that the metaproblem of deciding whether a given finite structure admits a coset-generating polymorphism (a ternary operation of the form (x,y,z) ↦ x y^{-1} z with respect to some group) is NP-complete, thereby answering an open question of Chen and Larose. It introduces a promise metaproblem parameterized by two polymorphism conditions Σ₁ and Σ₂, analogous to promise CSPs, and supplies sufficient conditions for membership in P and for NP-hardness. In particular, the promise metaproblem is shown to lie in P when Σ₁ asserts the existence of a Maltsev polymorphism and Σ₂ asserts the existence of an abelian heap polymorphism, even though neither unconditional metaproblem is known to be in P. The paper also characterizes the complexity of the creation-metaproblem for Maltsev polymorphisms under the promise that a heap polymorphism exists, showing it is in P if and only if there exists a uniform polynomial-time algorithm for CSPs admitting a heap polymorphism.

Significance. If the reductions and conditional algorithms hold, the work resolves a concrete open question in the algebraic theory of CSPs and supplies a new promise framework that can place certain polymorphism-existence problems in P even when the corresponding unconditional problems remain open. The explicit link between the creation-metaproblem and uniform CSP algorithms for heap polymorphisms strengthens the connection between polymorphism detection and tractability, which is of direct interest to the universal-algebra and constraint-satisfaction communities. The results rest on explicit reductions rather than circular or parameter-dependent arguments.

minor comments (3)
  1. [Abstract] The abstract refers to the operation as “coset-generating, or heaps” without a one-sentence reminder of the concrete form (x,y,z) ↦ x y^{-1} z; adding this would improve accessibility for readers outside universal algebra.
  2. In the definition of the promise metaproblem, the precise encoding of the input structure and the two polymorphism conditions Σ₁, Σ₂ should be stated explicitly (e.g., as relational signatures plus the two sets of identities) to avoid any ambiguity about how the promise is represented.
  3. The bibliography entry for Chen and Larose should be checked for completeness (year, venue, and page numbers) since the paper answers one of their questions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report accurately captures the main contributions, including the NP-completeness result for the coset-generating polymorphism metaproblem and the promise-metaproblem framework that places certain cases in P even when the unconditional versions remain open. We address the absence of specific major comments below.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes its main claims (NP-completeness of the coset-generating polymorphism metaproblem and conditional tractability/hardness results for the promise metaproblem) via explicit reductions from known problems and algorithmic constructions under stated polymorphism conditions Σ1/Σ2. These steps rely on standard universal-algebra definitions and complexity arguments rather than any self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained against external benchmarks and does not reduce any central result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard definition of polymorphisms as operations preserving all relations of a finite structure and on the algebraic characterization of heaps as coset operations from groups. No numerical parameters are fitted.

axioms (2)
  • domain assumption Finite structures are equipped with a finite signature and polymorphisms are required to preserve every relation of the structure.
    Standard definition in the CSP-universal-algebra literature invoked throughout the abstract.
  • domain assumption A heap polymorphism is exactly an operation of the form (x,y,z) maps to x y^{-1} z for some group operation on the domain.
    Definition used to formulate both the metaproblem and the promise version.

pith-pipeline@v0.9.0 · 5541 in / 1491 out tokens · 24691 ms · 2026-05-16T08:53:01.867544+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Algebraic approach to promise constraint satisfaction

    2 Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction.J. ACM, 68(4):28:1–28:66, 2021.doi:10.1145/3457606. 3 Libor Barto and Marcin Kozik. Absorbing subalgebras, cyclic terms and the constraint satisfaction problem.Logical Methods in Computer Science, 8/1(07):1–26,

    work page doi:10.1145/3457606 2021

  2. [2]

    6 Joshua Brakensiek and Venkatesan Guruswami

    URL:https://arxiv.org/abs/2505.11395,arXiv:2505.11395. 6 Joshua Brakensiek and Venkatesan Guruswami. An algorithmic blend of LPs and ring equations for promise CSPs. In Timothy M. Chan, editor,Proceedings of the Thirtieth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 436–455. SIAM, 2019....

    work page doi:10.1137/1.9781611975482.28 2019

  3. [3]

    The power of the combined basic LP and affine relaxation for promise CSPs.SIAM J

    9 Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Zivný. The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems.SIAM J. Comput., 49(6):1232–1248, 2020.doi:10.1137/20M1312745. 10 Simion Breaz, Tomasz Brzeziński, Bernard Rybołowicz, and Paolo Saracco. Heaps of modules and ...

    work page doi:10.1137/20m1312745 2020

  4. [4]

    12 Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, pages 319–330,

    work page 2017

  5. [5]

    Asking the metaquestions in constraint tractability.TOCT, 9(3):11:1–11:27, 2017.doi:10.1145/3134757

    15 Hubie Chen and Benoît Larose. Asking the metaquestions in constraint tractability.TOCT, 9(3):11:1–11:27, 2017.doi:10.1145/3134757. 16 Lenore Cowen, Wayne Goddard, and C. Esther Jesurum. Defective coloring revisited.J. Graph Theory, 24(3):205–219,

    work page doi:10.1145/3134757 2017

  6. [6]

    17 Victor Dalmau and Jakub Opršal

    doi:10.1002/(SICI)1097-0118(199703)24:3\<205:: AID-JGT2\>3.0.CO;2-T. 17 Victor Dalmau and Jakub Opršal. Local consistency as a reduction between constraint satisfaction problems, 2023.arXiv:2301.05084. 18 M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring.J. ACM, 23(1):43–49, January 1976.doi:10.1145/321921.321926. 19 Michael Gar...

    work page doi:10.1002/(sici)1097-0118(199703)24:3 2023

  7. [7]

    Kolaitis and Moshe Y

    22 Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-query containment and constraint satisfaction.J. Comput. Syst. Sci., 61(2):302–332, 2000.doi:10.1006/jcss.2000.1713. 23Serge Lang.Algebra. Springer,

    work page doi:10.1006/jcss.2000.1713 2000

  8. [8]

    24 Moritz Lichter and Benedikt Pago

    Revised third edition. 24 Moritz Lichter and Benedikt Pago. Limitations of affine integer relaxations for solving constraint satisfaction problems. In52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, volume 334 ofLIPIcs, M. Bodirsky, A. Weiß 17 xk,2 xk,1 u1 u2 u3 ... uq Figure 1For each va...

    work page 2025

  9. [9]

    Note thatq⩾3

    Here the verticesu1,...,u q correspond to those verticesvi,jwhere the literalLi,jis the variableX k. Note thatq⩾3. pages 166:1–166:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.doi:10.4230/ LIPICS.ICALP.2025.166. 25 Carlos V. G. C. Lima, Dieter Rautenbach, Uéverton S. Souza, and Jayme Luiz Szwarcfiter. Bipartizing with a matching. InCOCOA 20...

    work page doi:10.1007/978-3-030-04651-4 2025

  10. [10]

    37 Uri Zwick

    doi:10.1145/3402029. 32 Dmitriy Zhuk. Singleton algorithms for the constraint satisfaction problem,

    work page doi:10.1145/3402029

  11. [11]

    33 Dmitriy N

    URL: https://arxiv.org/abs/2509.18434,arXiv:2509.18434. 33 Dmitriy N. Zhuk. A proof of CSP dichotomy conjecture. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, pages 331–342,

    work page arXiv 2017

  12. [12]

    A Proof of Lemma 16 For convenience of the reader, we restate and give a proof of Lemma

    https://arxiv.org/abs/1704.01914. A Proof of Lemma 16 For convenience of the reader, we restate and give a proof of Lemma

    work page arXiv