Gap theorems for robust satisfiability: Boolean CSPs and beyond

DOI10.1016/J.TCS.2017.03.006MaRDI QIDQ527405zbMATH OpenOpenAlexFDO

Authors Lucy Ham

Publication date 11 May 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.09574

zbMATH Keywords

Booleanclone theoryconstraint satisfaction problemdichotomyrobust satisfiabilitytrichotomy

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: A computational problem exhibits a "gap property" when there is no tractable boundary between two disjoint sets of instances. We establish a Gap Trichotomy Theorem for a family of constraint problem variants, completely classifying the complexity of possible $$-hard gaps in the case of Boolean domains. As a consequence, we obtain a number of dichotomies for the complexity of specific variants of the constraint satisfaction problem: all are either polynomial-time tractable or $mathbfNP$-complete. Schaefer's original dichotomy for $extsfSAT$ variants is a notable particular case. Universal algebraic methods have been central to recent efforts in classifying the complexity of constraint satisfaction problems. A second contribution of the article is to develop aspects of the algebraic approach in the context of a number of variants of the constraint satisfaction problem. In particular, this allows us to lift our results on Boolean domains to many templates on non-Boolean domains.

Recommendations

• scientific article; zbMATH DE number 6861969
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• scientific article; zbMATH DE number 1670830
• Robust satisfiability for CSPs: hardness and algorithmic results
• A Dichotomy Theorem for Typed Constraint Satisfaction Problems

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Classifying the Complexity of Constraints Using Finite Algebras
• Closed systems of functions and predicates
• Closure properties of constraints
• Complexity and polymorphisms for digraph constraint problems under some basic constructions
• Complexity of conservative constraint satisfaction problems
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraints and universal algebra
• Constraints, consistency and closure
• Determining computational complexity from characteristic ``phase transitions
• Dichotomy on intervals of strong partial Boolean clones
• Frozen development in graph coloring
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• scientific article; zbMATH DE number 5268066 (Why is no real title available?)
• On generating all solutions of generalized satisfiability problems
• On the algebraic structure of combinatorial problems
• On the complexity of unfrozen problems
• Partial Polymorphisms and Constraint Satisfaction Problems
• Structure identification of Boolean relations and plain bases for co-clones
• The algebras of partial functions and their invariants
• The complexity of satisfiability problems
• The complexity of the counting constraint satisfaction problem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The constraint satisfaction problem and universal algebra
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The lattice of alter egos
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Universal algebra and hardness results for constraint satisfaction problems

Cited in

(7)

• Pushing the frontier of minimality
• Nonfinitely based ai-semirings with finitely based semigroup reducts
• scientific article; zbMATH DE number 6861969 (Why is no real title available?)
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Time complexity of constraint satisfaction via universal algebra
• Generalized satisfiability problems via operator assignments
• Flexible constraint satisfiability and a problem in semigroup theory

This page was built for publication: Gap theorems for robust satisfiability: Boolean CSPs and beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q527405)