The complexity of constraint satisfaction games and QCSP

DOI10.1016/j.ic.2009.05.003zbMath1188.68269MaRDI QIDQ840700

Andrei A. Bulatov, Hubie Chen, Andrei A. Krokhin, Ferdinand Börner, Peter G. Jeavons

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

zbMATH Keywords

complexity; algorithms; constraint satisfaction; games; polymorphisms; quantified constraint satisfaction problem

Mathematics Subject Classification ID

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

Tractability of quantified temporal constraints to the max, Constraint Satisfaction with Counting Quantifiers, Quantified Constraint Satisfaction Problem on Semicomplete Digraphs, Complexity of the game domination problem, The complexity of equivalence, entailment, and minimization in existential positive logic, Boolean max-co-clones, The complexity of counting quantifiers on equality languages, Hard constraint satisfaction problems have hard gaps at location 1, Low-level dichotomy for quantified constraint satisfaction problems, Quantified conjunctive queries on partially ordered sets, Quantified Conjunctive Queries on Partially Ordered Sets, On the Complexity of the Model Checking Problem

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