Low-level dichotomy for quantified constraint satisfaction problems

DOI10.1016/J.IPL.2011.07.010MaRDI QIDQ1944186zbMATH OpenOpenAlexFDO

Authors Barnaby Martin

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.3463

zbMATH Keywords

alternating logtimecomputational complexityquantified constraints

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: Building on a result of Larose and Tesson for constraint satisfaction problems (CSP s), we uncover a dichotomy for the quantified constraint satisfaction problem QCSP(B), where B is a finite structure that is a core. Specifically, such problems are either in ALogtime or are L-hard. This involves demonstrating that if CSP(B) is first-order expressible, and B is a core, then QCSP(B) is in ALogtime. We show that the class of B such that CSP(B) is first-order expressible (indeed, trivially true) is a microcosm for all QCSPs. Specifically, for any B there exists a C such that CSP(C) is trivially true, yet QCSP(B) and QCSP(C) are equivalent under logspace reductions.

Recommendations

• Relatively quantified constraint satisfaction
• Solving quantified constraint satisfaction problems
• Consistency for Quantified Constraint Satisfaction Problems
• On constraint satisfaction problems below P
• On constraint satisfaction problems below P
• Principles and Practice of Constraint Programming – CP 2004
• Meditations on quantified constraint satisfaction
• Non-dichotomies in Constraint Satisfaction Complexity
• Existentially restricted quantified constraint satisfaction
• Quantified constraint satisfaction problem on semicomplete digraphs

Cites work

• A Characterisation of First-Order Constraint Satisfaction Problems
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity classifications of Boolean constraint satisfaction problems
• Descriptive complexity: a logician's approach to computation.
• Logical Approaches to Computational Barriers
• On digraph coloring problems and treewidth duality
• On the complexity of H-coloring
• The complexity of constraint satisfaction games and QCSP
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• The complexity of satisfiability problems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Undirected connectivity in log-space
• Universal algebra and hardness results for constraint satisfaction problems

This page was built for publication: Low-level dichotomy for quantified constraint satisfaction problems

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