On constraint satisfaction problems below P

DOI10.1093/LOGCOM/EXU003MaRDI QIDQ2826030zbMATH OpenOpenAlexFDO

Authors László Egri

Publication date 7 October 2016

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

Full work available at URL https://arxiv.org/abs/1312.4428, https://drops.dagstuhl.de/opus/volltexte/2011/3232/

zbMATH Keywords

(nondeterministic) logspacebranching programsconstrain satisfaction problemsDatalog fragments

Mathematics Subject Classification ID

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

Abstract: Symmetric Datalog, a fragment of the logic programming language Datalog, is conjectured to capture all constraint satisfaction problems (CSP) in L. Therefore developing tools that help us understand whether or not a CSP can be defined in symmetric Datalog is an important task. It is widely known that a CSP is definable in Datalog and linear Datalog if and only if that CSP has bounded treewidth and bounded pathwidth duality, respectively. In the case of symmetric Datalog, Bulatov, Krokhin and Larose ask for such a duality (2008). We provide two such dualities, and give applications. In particular, we give a short and simple new proof of the result of Dalmau and Larose that "Maltsev + Datalog -> symmetric Datalog" (2008). In the second part of the paper, we provide some evidence for the conjecture of Dalmau (2002) that every CSP in NL is definable in linear Datalog. Our results also show that a wide class of CSPs-CSPs which do not have bounded pathwidth duality (e.g., the P-complete Horn-3Sat problem)-cannot be defined by any polynomial size family of monotone read-once nondeterministic branching programs.

Recommendations

• On constraint satisfaction problems below P
• Linear Datalog and Bounded Path Duality of Relational Structures
• scientific article; zbMATH DE number 2086640
• CSP duality and trees of bounded pathwidth
• Two new homomorphism dualities and lattice operations

Cited in

(14)

• Binary constraint satisfaction problems defined by excluded topological minors
• Low-level dichotomy for quantified constraint satisfaction problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The collapse of the bounded width hierarchy
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• On constraint satisfaction problems below P
• Descriptive complexity of list H-coloring problems in logspace: a refined dichotomy
• \(n\)-permutability and linear Datalog implies symmetric Datalog
• scientific article; zbMATH DE number 2086640 (Why is no real title available?)
• Linear Datalog and Bounded Path Duality of Relational Structures
• The pebble-relation comonad in finite model theory
• The pebble-relation comonad in finite model theory
• Symmetric linear arc monadic Datalog and gadget reductions
• CSP duality and trees of bounded pathwidth

This page was built for publication: On constraint satisfaction problems below P

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2826030)