Classifying the Complexity of Constraints Using Finite Algebras
From MaRDI portal
Publication:5317171
DOI10.1137/S0097539700376676zbMath1071.08002OpenAlexW2026753685MaRDI QIDQ5317171
Andrei A. Bulatov, Andrei A. Krokhin, Peter G. Jeavons
Publication date: 16 September 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539700376676
computational complexityconstraint satisfaction problemuniversal algebratractabilitydichotomy theoremsearch problemtractable algebra
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Quantified Constraint Satisfaction Problem on Semicomplete Digraphs ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ The Complexity of General-Valued CSPs ⋮ On Planar Boolean CSP ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ On the Complexity of the Model Checking Problem ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ Unnamed Item ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic ⋮ The Complexity of Counting Quantifiers on Equality Languages ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Unnamed Item ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs ⋮ Computing a partition function of a generalized pattern-based energy over a semiring ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ $(2+\varepsilon)$-Sat Is NP-hard ⋮ Non-dichotomies in Constraint Satisfaction Complexity ⋮ Quantified Constraint Satisfaction and the Polynomially Generated Powers Property ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Proof Complexity Meets Algebra ⋮ Min-Orderable Digraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ Quantified Constraints in Twenty Seventeen ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Varieties with few subalgebras of powers ⋮ On Maltsev Digraphs ⋮ On the CSP Dichotomy Conjecture ⋮ Constraint Satisfaction Parameterized by Solution Size ⋮ Solving equation systems in ω-categorical algebras ⋮ Max-Closed Semilinear Constraint Satisfaction ⋮ Unnamed Item ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized Complexity of the Workflow Satisfiability Problem ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Loop conditions for strongly connected digraphs ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ On m-Junctive Predicates on a Finite Set ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Unnamed Item ⋮ Approximability of the Maximum Solution Problem for Certain Families of Algebras ⋮ Testing the Complexity of a Valued CSP Language ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ CSP dichotomy for special triads ⋮ TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ Unnamed Item ⋮ АЛГЕБРЫ РИСА И КОНГРУЭНЦ-АЛГЕБРЫ РИСА В ОДНОМ КЛАССЕ АЛГЕБР С ОПЕРАТОРОМ И ОСНОВНОЙ ОПЕРАЦИЕЙ ПОЧТИ ЕДИНОГЛАСИЯ ⋮ Idempotent n -permutable varieties ⋮ Topological Birkhoff ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ The Complexity of Quantified Constraints Using the Algebraic Formulation ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems ⋮ A Logical Approach to Constraint Satisfaction ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ Introduction to the Maximum Solution Problem ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Solving CSPs Using Weak Local Consistency ⋮ Unnamed Item ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Unnamed Item ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side ⋮ On a stronger reconstruction notion for monoids and clones ⋮ Constraint satisfaction and semilinear expansions of addition over the rationals and the reals ⋮ Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Structural decompositions for problems with global constraints ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ The complexity of constraint satisfaction games and QCSP ⋮ Tropically convex constraint satisfaction ⋮ Dualities and algebras with a near-unanimity term ⋮ CSP for binary conservative relational structures ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ Strong partial clones and the time complexity of SAT problems ⋮ On planar valued CSPs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ More sublattices of the lattice of local clones ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Finite bands are finitely related ⋮ Is Polynomial Time Choiceless? ⋮ List-homomorphism problems on graphs and arc consistency ⋮ An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains ⋮ A strong Mal'cev condition for locally finite varieties omitting the unary type ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ On finite Taylor algebras ⋮ Conservative constraint satisfaction re-revisited ⋮ Enumerating homomorphisms ⋮ Maltsev digraphs have a majority polymorphism ⋮ Reconstructing the topology of clones ⋮ Majority constraints have bounded pathwidth duality ⋮ Generalised dualities and maximal finite antichains in the homomorphism order of relational structures ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ The power of propagation: when GAC is enough ⋮ Generic expression hardness results for primitive positive formula comparison ⋮ The complexity of surjective homomorphism problems-a survey ⋮ The wonderland of reflections ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Hybrid tractability of valued constraint problems ⋮ Colouring, constraint satisfaction, and complexity ⋮ The complexity of equality constraint languages ⋮ Computational complexity of auditing finite attributes in statistical databases ⋮ On Boolean primitive positive clones ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ An algebraic hardness criterion for surjective constraint satisfaction. ⋮ Qualitative constraint satisfaction problems: an extended framework with landmarks ⋮ Mal'tsev conditions, lack of absorption, and solvability. ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ On rainbow-free colourings of uniform hypergraphs ⋮ On bijunctive predicates over a finite set ⋮ Constants and finite unary relations in qualitative constraint reasoning ⋮ The complexity of counting quantifiers on equality languages ⋮ Tractability conditions for numeric CSPs ⋮ Key (critical) relations preserved by a weak near-unanimity function ⋮ The expressive power of valued constraints: Hierarchies and collapses ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ Complexity of clausal constraints over chains ⋮ The complexity of the list homomorphism problem for graphs ⋮ The expressive power of binary submodular functions ⋮ Quantified constraint satisfaction and the polynomially generated powers property ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ Approximability of clausal constraints ⋮ On Maltsev digraphs ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ Combinatorial problems raised from 2-semilattices ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ CSP duality and trees of bounded pathwidth ⋮ The \(C_{k}\)-extended graft construction ⋮ A note on some collapse results of valued constraints ⋮ A polynomial relational class of binary CSP ⋮ Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ Schaefer's Theorem for Graphs ⋮ Decidability of absorption in relational structures of bounded width. ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ Affine systems of equations and counting infinitary logic ⋮ Maximal infinite-valued constraint languages ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ On algebras with many symmetric operations ⋮ Determining the consistency of partial tree descriptions ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ On weak positive predicates over a finite set ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Best-case and worst-case sparsifiability of Boolean CSPs ⋮ CSP DICHOTOMY FOR SPECIAL POLYADS ⋮ Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}) ⋮ A quasi-Mal'cev condition with unexpected application. ⋮ Commutative idempotent groupoids and the constraint satisfaction problem. ⋮ Distance constraint satisfaction problems ⋮ \(H\)-coloring dichotomy revisited
