A Dichotomy Theorem for Nonuniform CSPs
Author:
- Andrei A. BulatovABAndrei A. Bulatov
Top Cited Papers
- 1 October 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 319-330
Abstract
In a non-uniform Constraint Satisfaction problem CSP(Γ), where Γ is a set of relations on a unite set A, the goal is to und an assignment of values to variables subject to constraints imposed on speciued sets of variables using the relations from Γ. The Dichotomy Conjecture for the non-uniform CSP states that for every constraint language Γ the problem CSP(Γ) is either solvable in polynomial time or is NP-complete. It was proposed by Feder and Vardi in their seminal 1993 paper. In this paper we confirm the Dichotomy Conjecture.Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction ProblemLogical Methods in Computer Science, 2012
- Complexity of conservative constraint satisfaction problemsACM Transactions on Computational Logic, 2011
- Varieties with few subalgebras of powersTransactions of the American Mathematical Society, 2009
- Undirected connectivity in log-spaceJournal of the ACM, 2008
- A Characterisation of First-Order Constraint Satisfaction ProblemsLogical Methods in Computer Science, 2007
- A dichotomy theorem for constraint satisfaction problems on a 3-element setJournal of the ACM, 2006
- On the algebraic structure of combinatorial problemsTheoretical Computer Science, 1998
- Constraints, consistency and closureArtificial Intelligence, 1998
- Closure properties of constraintsJournal of the ACM, 1997
- Polynomial interpolation and the Chinese Remainder Theorem for algebraic systemsMathematische Zeitschrift, 1975