Bounded width problems and algebras (Q997127)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounded width problems and algebras |
scientific article |
Statements
Bounded width problems and algebras (English)
0 references
20 July 2007
0 references
Many natural decision problems like SAT or graph \(k\)-colourability can be expressed in terms of a decision problem of the following type CSP\((A)\): Let \(A\) be a finite relational structure of finite type and let \(I\) be a given structure of the same type. Does there exist a homomorphism from \(I\) to \(A\)? To each relational structure \(A\) naturally an algebra \({\mathbf A}\) is associated whose structure determines the complexity of the associated decision problem. In the paper the authors investigate finite algebras arising from CSPs of bounded width, i.e. for which local consistency algorithms effectively decide the problem. They are able to prove that bounded width of a CSP implies that the variety generated by the associated algebra omits Hobby-McKenzie types 1 and 2. From this they can conclude the existence of CSPs that do not have bounded width. The paper concludes by giving several applications of this result by showing that various graph homomorphism problems do not have bounded width, i.e. that the corresponding graph-decision problems cannot be solved using local consistency algorithms.
0 references
decision problems
0 references
associated algebra
0 references
bounded width
0 references