The complexity of constraint satisfaction games and QCSP

DOI10.1016/J.IC.2009.05.003MaRDI QIDQ840700zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algorithmscomplexityconstraint satisfactiongamespolymorphismsquantified constraint satisfaction problem

Mathematics Subject Classification ID

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

Recommendations

• Unordered constraint satisfaction games
• Computer Science Logic
• Consistency for Quantified Constraint Satisfaction Problems
• STACS 2005
• Meditations on quantified constraint satisfaction

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A new tractable class of constraint satisfaction problems
• A Simple Algorithm for Mal'tsev Constraints
• An algebraic approach to multi-sorted constraints
• An algorithm to evaluate quantified Boolean formulae and its experimental evaluation
• Backjumping for quantified Boolean logic satisfiability
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Combinatorial problems raised from 2-semilattices
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity, appeal and challenges of combinatorial games
• Computer Science Logic
• Conjunctive-query containment and constraint satisfaction
• Constraints, consistency and closure
• scientific article; zbMATH DE number 3650557 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305704 (Why is no real title available?)
• scientific article; zbMATH DE number 1061261 (Why is no real title available?)
• scientific article; zbMATH DE number 2086640 (Why is no real title available?)
• scientific article; zbMATH DE number 2119676 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• Mathematical Foundations of Computer Science 2003
• On sentences which are true of direct unions of algebras
• On the algebraic structure of combinatorial problems
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On the complexity of some two-person perfect-information games
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004
• Resolution for quantified Boolean formulas
• STACS 2005
• The complexity of constraint satisfaction: an algebraic approach
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Undirected ST-connectivity in log-space

Cited in

(28)

• Low-level dichotomy for quantified constraint satisfaction problems
• Quantified conjunctive queries on partially ordered sets
• Unordered constraint satisfaction games
• Quantified conjunctive queries on partially ordered sets
• Complexity of the game domination problem
• On the complexity of the model checking problem
• Consistency for Quantified Constraint Satisfaction Problems
• The complexity of equivalence, entailment, and minimization in existential positive logic
• A Game Semantics of Idealized CSP
• Boolean max-co-clones
• Quantified Constraints in Twenty Seventeen
• Complexity of Unordered CNF Games
• The lattice and semigroup structure of multipermutations
• Complexity of unordered CNF games
• The complexity of quantified constraints using the algebraic formulation
• The complexity of counting quantifiers on equality languages
• Tractability of quantified temporal constraints to the max
• Constraint satisfaction with counting quantifiers
• Quantified constraint satisfaction problem on semicomplete digraphs
• Mathematical Foundations of Computer Science 2004
• Mathematical Foundations of Computer Science 2003
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• Constraint satisfaction problem: what makes the problem easy
• Surjective polymorphisms of directed reflexive cycles
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• _2P vs PSpace dichotomy for the quantified constraint satisfaction problem
• Graph homomorphism, monotone classes and bounded pathwidth
• Hard constraint satisfaction problems have hard gaps at location 1

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)