pith. sign in

arxiv: 1703.03021 · v2 · pith:ZHFFTIOFnew · submitted 2017-03-08 · 💻 cs.CC

A dichotomy theorem for nonuniform CSPs

Andrei A. Bulatov This is my paper
classification 💻 cs.CC
keywords dichotomynonuniformcomplexityconjectureconstraintcspsfederposed
0
0 comments X
read the original abstract

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

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems

    cs.LO 2026-04 unverdicted novelty 6.0

    A minion-theoretic characterization unifies the power of higher-level CSP algorithms and introduces an equivalent Z_p vector relaxation hierarchy that solves the dihedral D4 CSP and modular linear equations.

  2. SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks

    cs.CC 2026-04 unverdicted novelty 3.0

    All semilattices of Mal'cev blocks induce tractable CSP templates, reproving Bulatov's result while comparing two proofs of the CSP dichotomy theorem.