A dichotomy theorem for nonuniform CSPs
Author:
- Andrei A. BulatovABAndrei A. Bulatov
Preprint
Abstract
In this paper we prove the Dichotomy Conjecture on the complexity of nonuniform constraint satisfaction problems posed by Feder and Vardi.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Constraint Satisfaction Problems over semilattice block Mal'tsev algebrasInformation and Computation, 2019
- A Dichotomy Theorem for Nonuniform CSPs2017
- Conservative constraint satisfaction re-revisitedJournal of Computer and System Sciences, 2016
- A new line of attack on the dichotomy conjectureEuropean Journal of Combinatorics, 2016
- THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRAThe Bulletin of Symbolic Logic, 2015
- The collapse of the bounded width hierarchyJournal of Logic and Computation, 2014
- Varieties with few subalgebras of powersTransactions of the American Mathematical Society, 2009
- Existence theorems for weakly symmetric operationsAlgebra universalis, 2008
- Majority constraints have bounded pathwidth dualityEuropean Journal of Combinatorics, 2008
- The Complexity of Satisfiability Problems: Refining Schaefer’s TheoremLecture Notes in Computer Science, 2005