The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case

DOI10.1137/060668572zbMath1151.68025arXivcs/0607106OpenAlexW1968948791MaRDI QIDQ3532582

Hubie Chen

Publication date: 28 October 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityconstraint satisfactionuniversal algebraquantified satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

The complexity of constraint satisfaction games and QCSP ⋮ On the Complexity of the Model Checking Problem ⋮ \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ Unnamed Item ⋮ Quantified Constraint Satisfaction and the Polynomially Generated Powers Property ⋮ Quantified Constraints in Twenty Seventeen ⋮ Quantified constraint satisfaction and the polynomially generated powers property ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ The Complexity of Quantified Constraints Using the Algebraic Formulation ⋮ The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation

This page was built for publication: The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case