2024/02/15 by Tomáš Nagy, Nagy, Tomáš, Michael Pinsker +1
Engineering · #Advanced Theoretical and Applied Studies in Material Sciences and Geometry #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2402.09951
openalex publication_date 2024/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the `local consistency implies global consistency' principle of strict width among structures within the scope of the Bodirsky-Pinsker dichotomy conjecture for infinite-domain Constraint Satisfaction Problems (CSPs). Our main result implies that for certain CSP templates within the scope of that conjecture, having bounded strict width has a concrete consequence on the expressive power of the template called implicational simplicity. This in turn yields an explicit bound on the relational width of the CSP, i.e., the amount of local consistency needed to ensure the satisfiability of any instance. Our result applies to first-order expansions of any homogeneous k-uniform hypergraph, but more generally to any CSP template under the assumption of finite duality and general abstract conditions mainly on its automorphism group. In particular, it overcomes the restriction to binary signatures in the pioneering work of Wrona.