Quantified Constraint Satisfaction and the Polynomially Generated Powers Property

DOI10.1007/978-3-540-70583-3_17MaRDI QIDQ3519502zbMATH OpenOpenAlexFDO

Authors Hubie Chen

Publication date 19 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70583-3_17

Mathematics Subject Classification ID

Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Quantified constraint satisfaction and the polynomially generated powers property
• The complexity of quantified constraints using the algebraic formulation
• Principles and Practice of Constraint Programming – CP 2004
• STACS 2005
• Quantified constraint satisfaction problem on semicomplete digraphs

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 Simple Algorithm for Mal'tsev Constraints
• Capturing complexity classes by fragments of second-order logic
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity classifications of Boolean constraint satisfaction problems
• Computer Science Logic
• Generalized Majority-Minority Operations are Tractable
• scientific article; zbMATH DE number 3885853 (Why is no real title available?)
• scientific article; zbMATH DE number 4085614 (Why is no real title available?)
• On tractability and congruence distributivity
• Resolution for quantified Boolean formulas
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• The complexity of satisfiability problems
• The expressive rate of constraints
• Tractability and learnability arising from algebras with few subpowers
• Varieties with few subalgebras of powers

Cited in

(12)

• The size of generating sets of powers
• On the growth of generating sets for direct powers of semigroups.
• From complexity to algebra and back: digraph classes, collapsibility, and the PGP
• The complexity of quantified constraints using the algebraic formulation
• QCSP monsters and the demise of the chen conjecture
• Quantified constraint satisfaction problem on semicomplete digraphs
• Quantified constraint satisfaction on monoids
• Quantified constraint satisfaction and the polynomially generated powers property
• QCSP Monsters and the Demise of the Chen Conjecture
• Principles and Practice of Constraint Programming – CP 2004
• The school of V. B. Kudryavtsev at the chair of mathematical theory of intelligent systems: traditions and development
• A new line of attack on the dichotomy conjecture

This page was built for publication: Quantified Constraint Satisfaction and the Polynomially Generated Powers Property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3519502)