Low-level dichotomy for quantified constraint satisfaction problems

DOI10.1016/j.ipl.2011.07.010zbMath1260.68159arXiv1102.3463MaRDI QIDQ1944186

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

computational complexity; quantified constraints; alternating logtime

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Cites Work

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