The complexity of problems for quantified constraints

DOI10.1007/s00224-009-9194-6zbMath1204.68182OpenAlexW2000423606MaRDI QIDQ1959381

Henning Schnoor, Heribert Vollmer, Elmar Böhler, Nadia Creignou, Steffen Reith, Michael Bauland

Publication date: 6 October 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9194-6

zbMATH Keywords

computational complexityconstraint satisfactionsatisfiability problemsquantified formulas

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (5)

Parametrised Complexity of Satisfiability in Temporal Logic ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Complexity results for modal dependence logic ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Bases for Boolean co-clones
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Complexity of generalized satisfiability counting problems
• Complexity of constraints. An overview of current research themes
• Subtractive reductions and complete problems for counting complexity classes
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Polynomial Space Counting Problems
• PP is as Hard as the Polynomial-Time Hierarchy
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Undirected ST-connectivity in log-space
• The Complexity of Enumeration and Reliability Problems
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• Closure properties of constraints
• Computer Science Logic
• Function Algebras on Finite Sets
• Computer Science Logic
• The complexity of satisfiability problems
• Mathematical Foundations of Computer Science 2005
• Partial Polymorphisms and Constraint Satisfaction Problems
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: The complexity of problems for quantified constraints