The complexity of constraint satisfaction games and QCSP
DOI10.1016/J.IC.2009.05.003zbMATH Open1188.68269OpenAlexW2076946745MaRDI QIDQ840700FDOQ840700
Authors: Andrei A. Bulatov, Hubie Chen, Ferdinand Börner, P. Jeavons, Andrei Krokhin 
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
Recommendations
algorithmscomplexityconstraint satisfactiongamespolymorphismsquantified constraint satisfaction problem
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05)
Cites Work
- Title not available (Why is that?)
- Resolution for quantified Boolean formulas
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Complexity classifications of Boolean constraint satisfaction problems
- Title not available (Why is that?)
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Conjunctive-query containment and constraint satisfaction
- A new tractable class of constraint satisfaction problems
- Combinatorial problems raised from 2-semilattices
- Title not available (Why is that?)
- The complexity of constraint satisfaction: an algebraic approach
- A Simple Algorithm for Mal'tsev Constraints
- Title not available (Why is that?)
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- On sentences which are true of direct unions of algebras
- On the complexity of some two-person perfect-information games
- ON THE COMPLEXITY OF SOME COLORING GAMES
- Principles and Practice of Constraint Programming – CP 2004
- Undirected ST-connectivity in log-space
- Title not available (Why is that?)
- Complexity, appeal and challenges of combinatorial games
- Title not available (Why is that?)
- The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
- Computer Science Logic
- An algebraic approach to multi-sorted constraints
- Title not available (Why is that?)
- Title not available (Why is that?)
- An algorithm to evaluate quantified Boolean formulae and its experimental evaluation
- Backjumping for quantified Boolean logic satisfiability
- Mathematical Foundations of Computer Science 2003
- STACS 2005
- Logical Approaches to Computational Barriers
- Principles and Practice of Constraint Programming – CP 2004
Cited In (26)
- Tractability of quantified temporal constraints to the max
- Mathematical Foundations of Computer Science 2003
- Complexity of the game domination problem
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- Complexity of unordered CNF games
- Quantified conjunctive queries on partially ordered sets
- Quantified conjunctive queries on partially ordered sets
- The lattice and semigroup structure of multipermutations
- Constraint satisfaction with counting quantifiers
- Consistency for Quantified Constraint Satisfaction Problems
- Quantified Constraints in Twenty Seventeen
- On the complexity of the model checking problem
- A Game Semantics of Idealized CSP
- Surjective polymorphisms of directed reflexive cycles
- The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
- The complexity of equivalence, entailment, and minimization in existential positive logic
- Quantified constraint satisfaction problem on semicomplete digraphs
- Mathematical Foundations of Computer Science 2004
- Low-level dichotomy for quantified constraint satisfaction problems
- Complexity of Unordered CNF Games
- Boolean max-co-clones
- Hard constraint satisfaction problems have hard gaps at location 1
- The complexity of quantified constraints using the algebraic formulation
- The complexity of counting quantifiers on equality languages
- Constraint satisfaction problem: what makes the problem easy
- Unordered constraint satisfaction games
This page was built for publication: The complexity of constraint satisfaction games and QCSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q840700)
