Quantified constraint satisfaction and the polynomially generated powers property

DOI10.1007/s00012-011-0125-4zbMath1216.68124MaRDI QIDQ539977

Hubie Chen

Publication date: 1 June 2011

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00012-011-0125-4

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

08A70: Applications of universal algebra in computer science

03B10: Classical first-order logic

Related Items

Quantified Constraints in Twenty Seventeen, The Complexity of Quantified Constraints Using the Algebraic Formulation, Decomposing Quantified Conjunctive (or Disjunctive) Formulas, The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation, The size of generating sets of powers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The expressive rate of constraints
• Capturing complexity classes by fragments of second-order logic
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On the algebraic structure of combinatorial problems
• Resolution for quantified Boolean formulas
• 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
• Varieties with few subalgebras of powers
• Closure properties of constraints
• Constraint Satisfaction Problems of Bounded Width
• Computer Science Logic
• Generalized Majority-Minority Operations are Tractable
• On tractability and congruence distributivity
• Classifying the Complexity of Constraints Using Finite Algebras
• Computer Science Logic
• The complexity of satisfiability problems
• A Simple Algorithm for Mal'tsev Constraints