The complexity of constraint satisfaction games and QCSP

DOI10.1016/j.ic.2009.05.003zbMath1188.68269OpenAlexW2076946745MaRDI 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

complexityalgorithmsconstraint satisfactiongamespolymorphismsquantified constraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (18)

Quantified Constraint Satisfaction Problem on Semicomplete Digraphs ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ On the Complexity of the Model Checking Problem ⋮ Complexity of the game domination problem ⋮ Quantified conjunctive queries on partially ordered sets ⋮ The lattice and semigroup structure of multipermutations ⋮ Quantified Conjunctive Queries on Partially Ordered Sets ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ Surjective polymorphisms of directed reflexive cycles ⋮ Quantified Constraints in Twenty Seventeen ⋮ The complexity of equivalence, entailment, and minimization in existential positive logic ⋮ Boolean max-co-clones ⋮ The complexity of counting quantifiers on equality languages ⋮ Tractability of quantified temporal constraints to the max ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ The Complexity of Quantified Constraints Using the Algebraic Formulation ⋮ The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation

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

This page was built for publication: The complexity of constraint satisfaction games and QCSP