|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.
|
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
guest ::
