Publikace na Matematicko-fyzikální fakulta |
2011
Abstrakt
A central open question in the study of non-uniform constraint satisfaction problems (CSPs) is the dichotomy conjecture of Feder and Vardi stating that the CSP over a fixed constraint language is either NP-complete, or tractable. One of the main achievements in this direction is a result of Bulatov (LICS''03) confirming the dichotomy conjecture for conservative CSPs, that is, CSPs over constraint languages containing all unary relations.
Unfortunately, the proof is very long and complicated, and therefore hard to understand even for a specialist. This paper provides a short and transparent proof.