The complexity of constraint satisfaction games and QCSP
From MaRDI portal
Publication:840700
DOI10.1016/j.ic.2009.05.003zbMath1188.68269MaRDI QIDQ840700
Andrei A. Krokhin, Hubie Chen, Andrei A. Bulatov, Peter G. Jeavons, Ferdinand Börner
Publication date: 14 September 2009
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://ora.ox.ac.uk/objects/uuid:624b8559-7285-4bc3-bb14-d3c057919268
complexity; algorithms; constraint satisfaction; games; polymorphisms; quantified constraint satisfaction problem
68Q25: Analysis of algorithms and problem complexity
91A05: 2-person games
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Hard constraint satisfaction problems have hard gaps at location 1, Low-level dichotomy for quantified constraint satisfaction problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Backjumping for quantified Boolean logic satisfiability
- On the complexity of some two-person perfect-information games
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Conjunctive-query containment and constraint satisfaction
- An algorithm to evaluate quantified Boolean formulae and its experimental evaluation
- A new tractable class of constraint satisfaction problems
- Complexity, appeal and challenges of combinatorial games
- Resolution for quantified Boolean formulas
- Combinatorial problems raised from 2-semilattices
- 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 ST-connectivity in log-space
- ON THE COMPLEXITY OF SOME COLORING GAMES
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Computer Science Logic
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Mathematical Foundations of Computer Science 2003
- A Simple Algorithm for Mal'tsev Constraints
- STACS 2005
- On sentences which are true of direct unions of algebras
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Principles and Practice of Constraint Programming – CP 2003
- Logical Approaches to Computational Barriers
- Principles and Practice of Constraint Programming – CP 2004
- Principles and Practice of Constraint Programming – CP 2004
