# zbMATH — the first resource for mathematics

The collapse of the bounded width hierarchy. (English) Zbl 1353.68107
Summary: We show that every constraint satisfaction problem (CSP) over a fixed constraint language that has bounded relational width has also relational width $$(2,3)$$. Together with known results this gives a trichotomy: a CSP has either relational width $$1$$, or relational width $$(2,3)$$ (and no smaller relational width), or does not have bounded relational width. A consequence of this result is that if $$\Gamma$$ is a finite constraint language containing relations of arity at most $$k$$, then the CSP over $$\Gamma$$ either cannot be solved by a Datalog program, or can be solved by a Datalog program consisting of rules with at most $$\max \{3, k \}$$ variables and at most 2 variables in the head.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 68N17 Logic programming
Full Text: