CS Paper Radar

On Deciding the Constraint Loop Problem in Dimension Two

Daria Goliasova, Toghrul Karimov

cs.LO ·submitted 2026-10-29 16:22 UTC · v1

Abstract

Recently, Guilmant, Lefaucheux, Ouaknine, and Worrell [2] proved decidability of the termination problem for linear constraint loops over two real-valued variables, thus settling a wellknown open problem. Their algorithm is based on a theoretical result that such a loop does not terminate if and only if it has a witness of an infinite run of a specific shape. By analysing the structure of the witness carefully, we show that termination such loops can be decided in polynomial time, improving on the polynomial space bound argued by Guilmant et al. We also present an efficient implementation of the polynomial-time algorithm based on the satisfiability modulo theories (SMT) solver Z3.

Closest papers

Nearest neighbours by meaning across the whole index.

Towards Finite Satisfiability of PDL with Loops

cs.LO ·2026-10-11 ·Bartosz Jan Bednarczyk, Mikołaj Swoboda
theory similarity 0.63
Abstract · 52 pages, 8 figures, 2 tables. Under submission. This is a part of our ongoing work in progress: we are close to settling the finite satisfi…

Propositional Dynamic Logic (PDL) is a well-established modal logic of programs. Among its many extensions, the loop operator stands out for capturing the cyclic behaviour of programs: a world satisfies loop(pi) precisely when it can return to itself along a path matching the regular expression pi. While the satisfiability problem for the resulting logic LPDL was settled already in the 1980s, the decidability of its finite satisfiability problem has remained open ever since. The core difficulty is inherent to the finite setting: requiring and forbidding cycles at once is easily reconciled over arbitrary models, but over finite ones it defeats the existing finite-model-theoretic techniques. We make the first substantial progress towards closing this gap. We prove that finite satisfiability is ExpTime-complete for LPDL formulae (also in the presence of the converse operator) in negation normal form, under the restriction that every negated non-atomic loop has the form loop(pi^+) for some arbitrarily complex program pi -- a generalised form of self-reachability; positive occurrences of loops remain unrestricted. At the heart of our approach lies a novel way of representing intended finite models as their infinite, cactus-like unravellings: these are recognisable by two-way tree automata and satisfy a tailored omega-regular foldability condition that lets us finitise the accepted structures.

0.36

Discrete Temporal CSPs et al

cs.CC math.LO ·2026-10-15 ·Lukas Pieper
similarity 0.62
Abstract

We revisit the complexity classification of constraint satisfaction problems (CSPs) for first-order reducts of $(\mathbb{Z},<)$, established by Bodirsky, Martin, and Mottet in 2018. Following their approach, we give a self-contained proof of this classification, correcting several errors in the argument. We further show that, with the exception of cases arising from finite-domain CSPs, all tractable cases are solved by a well-known uniform algorithm, eliminating the need for the collection of ad-hoc algorithms used in the original paper. A central component of the proof allows the analysis to be restricted to first-order reducts of $(\mathbb{Z},<)$ that contain the successor relation. We substantially simplify this reduction and generalize the underlying construction. This generalization allows us to apply the same technique to first-order reducts of the triangular lattice graph and of infinite regular trees, yielding a complete complexity classification for these classes of structures, in particular a $\mathsf{P}$ versus $\mathsf{NP}$-complete dichotomy.

0.21

Two Variables and Two-Dimensional Structures

cs.LO ·2026-10-14 ·Bartosz Jan Bednarczyk, Daumantas Kojelis, Krzysztof Szymański
theory similarity 0.61
Abstract · 23 pages, 4 figures, 1 table. Under submission

We study the two-variable fragment FO^2 of first-order logic over two-dimensional structures. Formulae may employ two linear orders <=_1, <=_2, their successor relations S_1, S_2, and auxiliary predicates of any arity. Despite two decades of work, three cases of finite satisfiability in this setting were still open; we settle all three. First, finite satisfiability of FO^2 with one linear order and one successor relation, of the same or of a different order, is NExpTime-complete, even with arbitrary auxiliary predicates and constant symbols. This closes a gap left open by Manuel and Zeume (CSL 2013). As an application, a reduction based on swaps of adjacent elements shows that order-invariance and order-successor-invariance of FO^2 are coNExpTime-complete. This reproves the main result of Zeume and Harwath (LICS 2016) and settles their question on order-successor-invariance. Second, finite satisfiability of FO^2 with two linear orders is ExpSpace-hard, already without auxiliary non-unary predicates, matching the upper bound known since 2010. Our reduction combines Kieronski's encoding of alternating Turing machines with the classical fact that the pre-order and post-order traversals of a tree define its descendant relation. Third, with two linear orders and the successor of one of them, finite satisfiability is in ExpSpace even with arbitrary auxiliary predicates, improving the previous 2NExpTime bound and confirming a conjecture of Zeume and Harwath. Together with known results, our theorems show that in two dimensions, auxiliary (non-unary) predicates and constants come for free: with or without them, the complexities coincide. All our proofs are simple.

0.10

A Fast Algorithm for Maltsev Constraints

cs.CC cs.DS ·2026-10-06 ·Victor Lagerkvist
theory similarity 0.60
Abstract

The constraint satisfaction problem over a set of relations $Γ$ (CSP($Γ$)) is the computational problem of deciding if a set of constraints admits at least one solution. The classical complexity for finite-domain CSP($Γ$) is settled by the CSP dichotomy theorem: it is tractable if $Γ$ satisfies a non-trivial algebraic invariant and is NP-complete otherwise. However, not all these algebraic invariants result in efficient algorithms despite being theoretically tractable. A notable case that generalizes linear equations is that of Maltsev CSPs: an $n$-variable instance with $m$ constraints is solvable in roughly $O(n^8 \cdot m)$ time by Bulatov and Dalmau (SIAM J. Comput. 2006) or $O(n^4 \cdot m)$ time by Dyer and Richerby (SIAM J. Comput. 2013). At the same time, arguably, most "natural" and efficiently usable polynomial-time algorithms rarely exceed a quadratic or cubic time bound. In this paper we revisit Maltsev constraints with this question in mind and find a $O(n^2 \cdot m)$ algorithm (for finite languages, for infinite languages we in addition need to take the total size of the instance into account). The main novel idea is to not attempt to improve the bottleneck in Bulatov and Dalmau (the Fix-Values procedure) but to avoid it altogether with a slightly more refined approach that allows us to search through a smaller space.

0.25

Ideal Membership in Polynomial Calculus: Complexity and Reductions

cs.CC ·2026-09-23 ·Alex Bortolotti, Monaldo Mastrolilli
theory similarity 0.58
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

A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

cs.CC ·2026-11-05 ·Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy
theory similarity 0.58
Abstract

We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $Γ$ of $k$-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For $R\subseteq\{0,1\}^k$, let $d_R$ be the minimum degree of an integer-coefficient polynomial vanishing exactly on $R$ over the Boolean hypercube, and set $d_Γ=\max_{R\inΓ}d_R$. On polynomial-length streams, we obtain an $O_k(n^{d_Γ}\operatorname{polylog} n)$-space randomized algorithm and an $Ω_k(n^{d_Γ}/\log n)$ lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For $k\ge3$, $k$-XOR with literals has three distinct space complexities: $\widetildeΘ(n)$ for insertion-only satisfiability, $\widetildeΘ(n^{\lceil k/2\rceil})$ for strict-turnstile satisfiability, and $\widetildeΘ(n^k)$ for exact optimization in either model.

0.15

From Block Orthogonality to Decidability in Complex-Weighted Counting CSP

cs.CC ·2026-08-14 ·Chenghua Liu, Boning Meng
theory similarity 0.58
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

Maltsev Constraint Satisfaction Problems and Deterministic Logspace With Counting

cs.CC ·2026-09-25 ·Dejan Delic, Ali Syed
theoryhot direction similarity 0.57
Abstract

In this article, we prove that the problem of solving $\operatorname{CSP}(\mathbf{A})$, where $\mathbf{A}$ is a finite relational template which admits a Maltsev polymorphism is in a specific complexity class DET, which is related to the complexity of computing the determinant of a matrix with integer entries. Such a class is intimately related to well-studied MOD-logspace classes in the theory of computational complexity. To prove this fact, we develop a new algorithm for solving syntactically simple binary instances of Maltsev constraint satisfaction problems, rather different from the well-known Bulatov-Dalmau algorithm, which does not require the explicit use or knowledge of a Maltsev polymorphism of the template but, rather, utilizes a graph whose vertices are 2-generated subuniverses of $\mathbb{A}$, where $\mathbb{A}$ is the Maltsev algebra parametrizing $\operatorname{CSP}(\mathbf{A})$. The theoretical importance of this algorithm is reflected in two facts: (1) it places the problem $ \operatorname{CSP}(\mathbf{A})$ in a complexity class related to the deterministic logspace with counting, which, in itself, has a strong connection to a variety of standard algorithmic problems in linear algebra, and (2) it only makes use of the relational structure of the template without the need for the explicit use of a compatible Maltsev polymorphism, depending entirely on the strong ``symmetry" of constraints compatible with such polymorphisms and the knowledge of 2-generated subuniverses of $\mathbb{A}$.

0.49