Proof complexity of Mal’tsev CSP

Azza Gaysin · 2025

Read Proof complexity of Mal’tsev CSP by Azza Gaysin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00396.txt.

Introduction

Azza Gaysin studies how hard it is to prove that certain puzzle-like problems have no solution, in this 2025 paper. The problems, called Mal'tsev CSPs, are known to be solvable quickly by a classic algorithm. Gaysin asks whether short proofs exist that an unsolvable case truly has no answer.

Working inside a formal system that mirrors fast reasoning, Gaysin shows the classic algorithm is sound. That means the statements claiming no solution admit short proofs in a strong proof system. A small tweak extends the result to a related algorithm for a wider problem class. The work links practical algorithms to the theory of proof length.

Catalog record

CREATORAzza Gaysin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-00396

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Proof complexity of Mal’tsev CSP Azza Gaysin Abstract Constraint Satisfaction Problems (CSPs) form a broad class of combinatorial problems, which can be formulated as homomorphism problems between relational structures. The CSP dichotomy theorem classifies all such problems over finite domains into two categories: NP-complete and polynomial-time [ 9 ] , [ 20 ] . Polynomial-time CSPs can be further subdivided into smaller subclasses. Mal’tsev CSPs are defined by the property that every relation in the problem is invariant under a Mal’tsev operation, a ternary operation μ \mu satisfying μ ⁡ ( x , y , y ) = μ ⁡ ( y , y , x ) = x \mu(x,y,y)=\mu(y,y,x)=x for all x , y x,y . Bulatov and Dalmau proved that Mal’tsev CSPs are solvable in polynomial time, presenting an algorithm for such CSPs [ 7 ] . The negation of an unsatisfiable CSP instance can be expressed as a propositional tautology. We formalize the algorithm for Mal’tsev CSPs within bounded arithmetic V 1 V^{1} , which captures polynomial-time reasoning and corresponds to the extended Frege proof system. We show that V 1 V^{1} proves the soundness of Mal’tsev algorithm, implying that tautologies expressing the non-existence of a solution for unsatisfiable instances of Mal’tsev CSPs admit short extended Frege proofs. In addition, with small adjustments, we achieved an analogous result for Dalmau’s algorithm that solves generalized majority-minority CSPs - a common generalization of near-unanimity operations and Mal’tsev operations. 1 Introduction Constraint Satisfaction Problems (CSPs) encompass a broad class of combinatorial problems. In a CSP instance, the goal is to assign values from a finite domain to a set of variables such that all specified constraints are simultaneously satisfied. A constraint is defined as a pair consisting of a tuple of variables, called scope, and a relation that specifies the allowed combinations of values for the variables in that scope, called constraint relation. If we restrict the set of relations to a set \Gamma , called constraint language, we denote an instance of the CSP over that set as \operatorname{CSP}(\Gamma) . An equivalent formulation of CSPs is in terms of homomorphisms between relational structures. Given a relational structure \mathcal{A} , the problem \operatorname{CSP}(\mathcal{A}) asks, for an input structure \mathcal{X} over the same relational vocabulary, whether there exists a homomorphism from \mathcal{X} to \mathcal{A} . Despite their general NP-completeness [ 9 ] , [ 20 ] , a rich algebraic theory provides precise criteria for tractable subclasses. These criteria are typically phrased in terms of the existence of so-called polymorphisms - operations on the domain that preserve all constraint relations. A well-studied tractable subclass is formed by Mal’tsev CSPs, where the template admits a Mal’tsev polymorphism, that is, a ternary operation \mu on a domain A satisfying \mu(x,y,y)=\mu(y,y,x)=x for all x,y\in A . We say that CSP( \mathcal{A} ) is Mal’tsev, if every relation from \mathcal{A} is preserved by a Mal’tsev polymorphism. Mal’tsev CSPs comprise, in particular, affine problems and the general subgroup problem. Bulatov and Dalmau [ 7 ] proved that Mal’tsev CSPs are solvable in polynomial time by developing an algorithm based on the notion of compact representations. When viewed as a homomorphism problem, each instance \mathcal{X} of \operatorname{CSP}(\mathcal{A}) can be encoded as a conjunction of a simple and easily interpretable set of clauses, denoted by \operatorname{CNF}(\mathcal{X},\mathcal{A}) ; see, for example, the constructions in [ 1 ] , [ 15 ] . This set is built from propositional atoms p_{ij} , one for each element i in the structure \mathcal{X} and each element j in \mathcal{A} , representing the possible assignments in a homomorphism between the relational structures. For unsatisfiable instances of \operatorname{CSP}(\mathcal{A}) , the negation of \operatorname{CNF}(\mathcal{X},\mathcal{A}) , which expresses that no homomorphism from \mathcal{X} to \mathcal{A} exists, is a tautology of size polynomial in the sizes of \mathcal{X} and \mathcal{A} . This opens the possibility of analyzing tractable subclasses of CSPs using the methods of proof complexity. The question is, in which propositional proof systems such tautologies admit short proofs. The first to study this correspondence were Atserias and Ochremiak [ 1 ] . They studied the impact of standard efficient reductions between constraint languages on the complexity of their propositional proofs. We considered the correspondence for various tractable subclasses of CSPs in [ 15 ] , [ 16 ] and [ 17 ] , providing formalizations in different theories of bounded arithmetic. Each theory of bounded arithmetic is associated with a propositional proof system in the sense that, if a universal statement is provable in the theory, then all of its propositional translations admit polynomial-size proofs in the corresponding proof system. In this paper, we adapt our framework to Mal’tsev CSPs. Our main result is that the soundness of Mal’tsev algorithm can be proved in a theory of bounded arithmetic V^{1} , which captures polynomial-time reasoning. By soundness, we mean that whenever the algorithm outputs a negative answer, the instance is indeed unsatisfiable. By the known correspondence between the theory and the extended Frege (EF) proof system, it follows that the tautologies \neg\operatorname{CNF}(\mathcal{X},\mathcal{A}) encoding the non-existence of solutions for unsatisfiable instances admit polynomial-size extended Frege proofs. While for satisfiable instances \mathcal{X} of CSP( \mathcal{A} ) Mal’tsev algorithm produces a homomorphism from \mathcal{X} to \mathcal{A} as a witness of a positive answer, for unsatisfiable instances, polynomial-size extended Frege proofs can be regarded as independent witnesses of the correctness of negative answers to \operatorname{CSP}(\mathcal{A}) . In addition, we obtained an analogous result for Dalmau’s algorithm [ 13 ] , which solves generalized majority-minority CSPs - a common generalization of near-unanimity operations and Mal’tsev operations. A k -ary operation on A is called generalized majority-minority if for all a,b\in A , \varphi(x,y,\ldots,y)=\varphi(y,x,\ldots,y)=\ldots.=\varphi(y,y,\ldots,x)=y or \varphi(x,y,\ldots,y)=\varphi(y,y,\ldots,x)=x for all x,y\in\{a,b\} . Dalmau’s algorithm is very similar to the Mal’tsev algorithm, and its formalization requires only minor adjustments. The structure of the paper is as follows. Sections 2.1 and 2.2 review essential concepts from universal algebra, introduce Mal’tsev and generalized majority-minority (GMM) algebras, and present key generating theorems. Sections 2.3 and 2.4 define constraint satisfaction problems (CSPs), with particular focus on Mal’tsev CSPs, and outline the core ideas behind the Mal’tsev algorithm. In Section 2.5 , we provide background from proof complexity and bounded arithmetic, and explain the correspondence between these two areas. Section 2.6 introduces several general auxiliary functions and relations definable within theory V^{1} . Section 4 is dedicated to the formalization of the Mal’tsev algorithm and is structured in three main parts. Sections 3.1 , 3.2 , and 3.3 establish the framework, formalize the necessary concepts from universal algebra, and describe the correspondence between relational structures and algebras. Section 3.4 contains the formalization of all algorithmic subroutines along with proofs of their correctness. In Section 3.5 , we formulate and prove the main universal statement and derive the upper bound for Mal’tsev CSPs. Finally, Section 4 extends these results to Dalmau’s algorithm and states the corresponding upper bound for GMM CSPs. 2 Preliminaries 2.1 Basic universal algebra notions and results This subsection draws on results from [ 2 ] and [ 3 ] . Several definitions and statements are adapted from [ 10 ] . For any non-empty set A and any natural number n , a function f\colon A^{n}\to

Read the complete text