Low-level dichotomy for quantified constraint satisfaction problems

DOI10.1016/j.ipl.2011.07.010zbMath1260.68159arXiv1102.3463OpenAlexW1997502611MaRDI 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 complexityquantified constraintsalternating logtime

Mathematics Subject Classification ID

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

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

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