The collapse of the bounded width hierarchy

DOI10.1093/logcom/exu070zbMath1353.68107OpenAlexW2314918483MaRDI QIDQ2826031

Libor Barto

Publication date: 7 October 2016

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/logcom/exu070

zbMATH Keywords

constraint satisfaction problemDatalogbounded widthlocal consistencyPrague instancerelational width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic programming (68N17)

Related Items

Tractability in constraint satisfaction problems: a survey, CLAP: A New Algorithm for Promise CSPs, The Complexity of General-Valued CSPs, Sherali-Adams Relaxations for Valued CSPs, Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties, Constraint Satisfaction Problems Solvable by Local Consistency Methods, Equivariant algorithms for constraint satisfaction problems over coset templates, The Power of Sherali--Adams Relaxations for General-Valued CSPs, Unnamed Item, Unnamed Item, The Complexity of Valued CSPs, A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties, Robustly Solvable Constraint Satisfaction Problems, Unnamed Item, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, Solving CSPs Using Weak Local Consistency, Characterizations of several Maltsev conditions.