CS Paper Radar

Promise Systems of Equations over Magmas with Identity and over Algebras in Congruence Modular Varieties

Nick Jamesson

cs.CC ·submitted 2026-09-03 07:28 UTC · v1

Abstract

We study the computational complexity of solving promise systems of equations over finite algebras. Given two algebras $\mathbf{A}$ and $\mathbf{B}$ with a homomorphism from $\mathbf{A}$ to $\mathbf{B}$, the promise system of equations problem is to determine if an input system of equations has a solution in $\mathbf{A}$ or not even in $\mathbf{B}$. We generalize the results of Larrauri, Mottet, and Živný [ACM ToCL'26] to obtain a $\mathbf{P}-\mathbf{NP}$-hard dichotomy result for promise systems of equations over a class of algebras which contains all monoids, and a dichotomy result for promise systems of equations over algebras in a congruence modular variety. We then consider the metaproblem for promise systems of equations over algebras in a congruence modular variety: given finite algebras $\mathbf{A}$ and $\mathbf{B}$ such that $\mathbf{A}$ is in a congruence modular variety, we show there is a quasi-polynomial time algorithm for determining whether or not the associated promise system of equations problem is in $\mathbf{P}$.

Closest papers

Nearest neighbours by meaning across the whole index.

Structure and Complexity of 2-Nilpotent Mal'cev Algebras

cs.CC math.RA ·2026-08-19 ·Patrick Wynne
similarity 0.61
Abstract

We investigate the structure of central extensions for algebras in a congruence modular variety. We use a multisorted algebraic object called a clonoid to understand the term clone of such a central extension. We develop the difference clonoid of such a central extension and use it to show that the number of $2$-step nilpotent algebras on a fixed finite set is finite if and only if the set is of squarefree order. The subpower membership problem for a finite algebraic structure $\mathbb{A}$ is the problem of deciding on input $a_1,\dots,a_k, b \in A^n$, whether $b$ is in the subalgebra of $\mathbb{A}^n$ generated by $a_1, \dots, a_k$. We show that for a large class of nilpotent Mal'cev algebras the subpower membership problem is solvable in polynomial time, in particular for $2$-step nilpotent Mal'cev algebras of squarefree order.

0.26

Finite $\mathbf{BM}$-algebras and fixed-point combinators

cs.LO math.LO ·2026-10-27 ·Takuma Imamura
theory similarity 0.59
Abstract

We study algebras for the $\mathbf{BM}$-, $\mathbf{BI}$-, and $\mathbf{BMI}$-fragments of combinatory logic, where $\mathbf{B} xyz \to_{w} x\left(yz\right)$, $\mathbf{M} x \to_{w} xx$ and $\mathbf{I} x \to_{w} x$. We prove that every finite $\mathbf{BM}$-algebra $\mathcal{A}$ contains an element $Y$ satisfying $Yx = x\left(Yx\right)$ for all $x\in A$. Moreover, a single closed $\mathbf{BM}$-term represents such an element in every finite $\mathbf{BM}$-algebra. On the other hand, we show that there exists an infinite $\mathbf{BMI}$-algebra with no such element. Consequently, the variety of $\mathbf{BM}$-algebras is not generated by finite $\mathbf{BM}$-algebras. We also characterise finite $\mathbf{BI}$-algebras as finite semigroups with two distinguished left units $B$ and $I$, and finite $\mathbf{BMI}$-algebras as finite idempotent semigroups with three distinguished left units $B$, $M$ and $I$.

0.25

Ideal Membership in Polynomial Calculus: Complexity and Reductions

cs.CC ·2026-09-23 ·Alex Bortolotti, Monaldo Mastrolilli
theory similarity 0.56
Abstract

The Ideal Membership Problem (IMP) asks whether a polynomial f belongs to an ideal <p_1, ..., p_m> of Q[x_1, ..., x_n]. Polynomial Calculus (PC) certifies membership by deriving f from the generators, and a degree-d derivation needs at most n^O(d) steps. We write PC-IMPd for the problem of producing a degree-bounded PC certificate, and call it solvable when one is guaranteed to exist and can be found in time n^O(d). Over Q, unlike over finite fields, a derivation may need exponentially many bits. We study PC-IMPd on instances arising from constraint satisfaction problems, and ask for which constraint languages L it is solvable. Our main contribution is a reduction framework for PC-IMPd, based on pp-definitions, pp-interpretations, and pp-encodings, that mirrors the algebraic approach to CSP complexity. Solvability is preserved by these constructions and, in the language of algebras, by passing to subalgebras, finite direct powers, and homomorphic images. We obtain new tractable classes over ternary and larger domains: every language closed under the median operation on a finite chain has solvable PC-IMPd, by reduction to the Boolean majority algebra, and in particular so does every language over {0, 1, 2} closed under a fixed-value majority. This also places IMPd(L) in P for such languages, advancing the classification of IMPd over ternary domains. In the process, we settle the last open case of the Boolean dichotomy for IMPd(L) and complete the Boolean classification of PC-IMPd(L) with an unconditional lower bound for an instance of PC-IMP1. A recent PC-to-SoS simulation reduces degree-automatability of Sum-of-Squares (the open problem of finding a degree-d SoS proof in time n^O(d) when one exists) to solvability of PC-IMPd. Each new tractable class therefore yields a family of constraint systems on which SoS proofs are degree-automatable.

0.24

Abelian embeddings make useful promises: approximation of detrivialised equations

cs.CC cs.DMcs.DS ·2026-11-03 ·Tamio-Vesa Nakajima, Zephyr Verwimp, Stanislav Živný
theory similarity 0.56
Abstract

We study the following family of search problems: given a system of equations $x+y+z\equiv 0\pmod p$ promised to admit a solution that is nonconstant on every equation, find a $c$-colouring of the variables that makes no equation monochromatic. For $p\in\{2,3\}$, the problem recovers known tractable Promise Constraint Satisfaction Problems (PCSPs). For $p > 3$, we obtain a complete complexity classification: the problem is polynomial-time solvable for $c \geq 4$, yet even its decision version is NP-hard for $c = 3$, and it is not well-defined for $c = 2$. Our main conceptual contribution is a general tractability framework for PCSPs based on Abelian embeddings, a notion introduced by Bhangale, Khot, and Minzer [STOC 2022] in the study of quantitative approximation of satisfiable CSPs. We show that suitable Abelian embeddings yield polynomial-time PCSP reductions realised by singleton algorithms in the sense of Zhuk [FOCS 2026]. On the hardness side, the promise relation is far removed from the reconfigurable regime covered by the conditional hardness framework of Banakh, Barsukov, and Nakajima [LICS 2026]; our proof instead relies on a new additive-combinatorial rigidity theorem classifying special $3$-colourings of $\mathbb{Z}_p$.

0.29

Preorder Preservation versus Congruence Preservation

cs.FL math.LO ·2026-08-23 ·Patrick Cégielski, Irène Guessarian
theory similarity 0.56
Abstract

Looking at some monoids and (semi)rings (natural numbers, integers and $p$-adic integers), and more generally, residually finite algebras (in a strong sense), we prove the equivalence of two ways for a function $f$ on such an algebra to behave like the operations of the algebra. The first way is to preserve congruences or stable preorders. The second way is to demand that, for any (recognizable) set $L$, a suitably chosen lattice (or Boolean algebra) generated by $L$ be closed under inverse images by the function $f$.

0.25

Approximate Polynomial Satisfiability is in the Counting Hierarchy

cs.CC ·2026-09-30 ·Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell
theory similarity 0.53
Abstract

The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image of a given polynomial map. Specifically, for a field $k$ with algebraic closure~$K$, the problem asks whether $\boldsymbol 0 \in\overline{\boldsymbol f(K^n)}$ for a polynomial map $\boldsymbol f=(f_1,\ldots,f_m)$ with $f_i\in k[X_1,\ldots,X_n]$. APS is a natural topological analogue of Hilbert's Nullstellensatz, namely the question of whether a given system of polynomial equations has a common zero. APS captures several problems in algebraic complexity, including border rank, hitting sets for border classes, and null-cone membership; it is known to be NP-hard and in PSPACE. We show that APS lies in the Counting Hierarchy (CH) over both the rationals and finite fields, substantially improving the known PSPACE upper bound. Our proof builds on a recent breakthrough due to Andrews, Garg, and Schost (FOCS 2026) on deciding Hilbert's Nullstellensatz in CH. As a corollary, our result improves the complexity of certifying hitting sets for border classes from PSPACE to CH. We also give a polynomial-time reduction of Hilbert's Nullstellensatz to APS, valid in any characteristic. In characteristic zero, we give a reduction of APS to the decision problem for the existential theory of real closed fields. Overall, our results place approximate polynomial satisfiability closer in complexity to exact polynomial feasibility and as a byproduct give improved complexity bounds for several problems arising in approximative complexity.

0.53

Discrete-time polynomial systems with inputs and outputs: structure, reachability, observability, and minimal realizations

eess.SY math.OC ·2026-09-29 ·Eduardo D. Sontag
similarity 0.52
Abstract

We study the realization problem for discrete-time input/output polynomial systems. These are formalized using tools from commutative algebra and algebraic geometry as systems whose state spaces are algebraic varieties, or more abstractly the set of k-points of an affine k-scheme, where k is an arbitrary infinite field. The input/output behaviors of such systems are described by "polynomial response maps" in which outputs are polynomial functions of past inputs. The main results show that every polynomial response map admits a canonical (quasi-reachable and algebraically observable) realization, which is unique up to isomorphism. The key to the approach is to linearize dynamics by considering a "dual" system in which states are functions defined on states. Finite dimensionality of the canonical realization, and its polynomiality, are characterized in terms of the space, algebra, and field of observables of the map, as well as in terms of algebraic input/output difference equations, and by a Jacobian rank criterion. A particular subclass consists of the maps that we call "bounded," defined by the property that their degree in the past inputs is uniformly bounded. Bounded maps are shown to be finitely realizable if and only if they are realizable by finite-dimensional state-affine systems, whose theory in turn reduces to that of rational formal power series. We also study the lattice of quasi-reachable realizations of a given map, including normal realizations. This work is an update of the PhD thesis written by the author in 1976; connections to recent work are briefly discussed in the last section.

0.38

From Block Orthogonality to Decidability in Complex-Weighted Counting CSP

cs.CC ·2026-08-14 ·Chenghua Liu, Boning Meng
theory similarity 0.52
Abstract · 68 pages; revised proof and exposition, including a correction; Lean repository linked

In a landmark JACM paper recognized with the 2021 Gödel Prize, Cai and Chen established a complexity dichotomy for counting CSPs over arbitrary finite domains with algebraic complex weights. Their tractability criterion consists of three conditions on the infinite family of functions obtained from CSP instances by summing out some variables: the Block Orthogonality and Type Partition conditions, and a Mal'tsev polymorphism condition on support and row-equivalence relations. They left open whether this criterion is decidable from the finite set of constraint functions. We resolve this question by giving a total exact algorithm for every $q$-element domain ($q\ge 1$), with algebraic weights encoded exactly. We also prove that the Block Orthogonality condition implies the other two conditions, reducing the tractability criterion to a single structural property. We obtain similar decidability and structural results for Lin's tractability criterion for $\#\mathrm{CSP}^{d}$, where each variable occurs a multiple of $d$ times. Our method first shows that every failure of Block Orthogonality can be witnessed by a generated function of arity at most $q^2+1$. At each such arity, we reduce checking infinitely many generated functions to finitely many exact algebraic tests, using tensor products and a pinned extension of Young's all-instance isomorphism theorem. For the structural implication, we use powers of generated functions to control complex cancellation and construct functions whose supports encode row equivalence. These constructions yield the Type Partition and Mal'tsev polymorphism conditions.

0.10