Complexity of Homogeneous Co-Boolean Constraint Satisfaction Problems

In this short note we show a dichotomy theorem for every finite domain D of CSP built upon graphs of homogeneous co-Boolean functions, i.e., unary functions sharing the Boolean range in D.

Computer Science Mathematics

View graph Source

Paper

References (7)

01Classifying the Complexity of Constraints Using Finite AlgebrasA. Bulatov, P. Jeavons, A. Krokhin2005 · SIAM journal on computing (Print) · 605 citations

02Dichotomies for classes of homomorphism problems involving unary functionsT. Feder, Florent R. Madelaine, I. A. Stewart2004 · Theoretical Computer Science · 32 citations

03The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group TheoryT. Feder, Moshe Y. Vardi1999 · SIAM journal on computing (Print) · 1.1k citations

04On the Algebraic Structure of Combinatorial ProblemsP. Jeavons1998 · Theoretical Computer Science · 406 citations

05Closure properties of constraintsP. Jeavons, David A. Cohen, M. Gyssens1997 · JACM · 508 citations

06The complexity of satisfiability problemsT. Schaefer1978 · Symposium on the Theory of Computing · 2.1k citations

07A dichotomy theorem for constraint satisfaction problems on a 3-element setA. Bulatov2006 · JACM · 337 citations

Similar papers

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hardLeonid Dorochko, Michal Wrona2026 · arXiv.org · 0 citations In Library

The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction ProblemsL. Barto, M. Pinsker2016 · Logic in Computer Science · 89 citations In Library

Conservative constraint satisfaction re-revisitedA. Bulatov2014 · Journal of computer and system sciences (Print) · 39 citations In Library

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean DichotomyJoshua Brakensiek, V. Guruswami2017 · Electron. Colloquium Comput. Complex. · 68 citations In Library

An Effective Dichotomy for the Counting Constraint Satisfaction ProblemM. Dyer, David Richerby2010 · SIAM journal on computing (Print) · 96 citations In Library

Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A SurveyMiguel Couceiro, L. Haddad, Victor Lagerkvist2019 · IEEE International Symposium on Multiple-Valued Logic · 11 citations In Library

Strict width for Constraint Satisfaction Problems over homogeneous strucures of finite dualityTom'avs Nagy, M. Pinsker2024 · arXiv.org · 1 citation In Library

Approximate counting for complex-weighted Boolean constraint satisfaction problemsT. Yamakami2010 · Information and Computation · 16 citations In Library

The Dichotomy for Conservative Constraint Satisfaction is Polynomially DecidableClément Carbonnel2016 · International Conference on Principles and Practice of Constraint Programming · 8 citations In Library

Complexity Classification in Infinite-Domain Constraint SatisfactionM. Bodirsky2012 · arXiv.org · 100 citations In Library

Patents near this paper

HANDLING OF SATISFACTION AND CONFLICTS IN A QUANTIFIED BOOLEAN FORMULA SOLVERUS 7,577,625 · MICROSOFT CORPORATION · 2009 DETERMINING SATISFIABILITY OF A FUNCTION WITH ARBITRARY DOMAIN CONSTRAINTSUS 8,001,072 · MICROSOFT CORPORATION · 2011 METHOD AND APPARATUS FOR SOLVING CONSTRAINTSUS 7,107,553 · SYNOPSYS, INC. · 2006 CONSTRAINT SATISFACTION PROBLEM SOLVERUS 8,392,348 · INTERNATIONAL BUSINESS MACHINES CORPORATION · 2013 CONSTRAINT SATISFACTION PROBLEM SOLVING USING CONSTRAINT SEMANTICSUS 8,781,986 · INTERNATIONAL BUSINESS MACHINES CORPORATION · 2014

Source of record

arXiv