Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
In this paper we prove the Dichotomy Conjecture on the complexity of nonuniform constraint satisfaction problems posed by Feder and Vardi.
arXiv comments
Apart from correcting typos and inaccuracies, this version of the paper is different from the first arXiv version in the following ways: A self-contained high level presentation of the main results is added; the Preliminaries section is extended, several proofs are reorganized and expanded for improved readability
The solution to the Dichotomy Conjecture for Constraint Satisfaction Problems [1] (also [2], but this proof is much more difficult). This gives a clear dividing line between the types of problems that are easy to solve exactly and the types of problems that are difficult to…
The solution to the Dichotomy Conjecture for Constraint Satisfaction Problems [1] (also [2], but this proof is much more difficult). This gives a clear dividing line between the types of problems that are easy to solve exactly and the types of problems that are difficult to…
ceviView on HNParent context