×

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: DOI