Gap theorems for robust satisfiability: Boolean CSPs and beyond

DOI10.1016/j.tcs.2017.03.006zbMath1370.68128arXiv1610.09574OpenAlexW2605361762MaRDI QIDQ527405

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

constraint satisfaction problemdichotomyclone theorytrichotomyBooleanrobust satisfiability

Mathematics Subject Classification ID

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

Related Items (4)

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Pushing the frontier of minimality ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ Nonfinitely based ai-semirings with finitely based semigroup reducts

Cites Work

• Unnamed Item
• Unnamed Item
• Structure identification of Boolean relations and plain bases for co-clones
• Universal algebra and hardness results for constraint satisfaction problems
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Constraints and universal algebra
• Dichotomy on intervals of strong partial Boolean clones
• Closed systems of functions and predicates
• On the complexity of unfrozen problems
• THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
• THE LATTICE OF ALTER EGOS
• Complexity of conservative constraint satisfaction problems
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The algebras of partial functions and their invariants
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• On generating all solutions of generalized satisfiability problems
• Complexity and polymorphisms for digraph constraint problems under some basic constructions
• Classifying the Complexity of Constraints Using Finite Algebras
• Determining computational complexity from characteristic ‘phase transitions’
• The complexity of the counting constraint satisfaction problem
• The complexity of satisfiability problems
• Partial Polymorphisms and Constraint Satisfaction Problems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Frozen development in graph coloring

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