A dichotomy theorem for nonuniform CSPs

Abstract

In this paper we prove the Dichotomy Conjecture on the complexity of nonuniform constraint satisfaction problems posed by Feder and Vardi.

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