The complexity of problems for quantified constraints
type: Item
instance of: scholarly article
title: The complexity of problems for quantified constraints
zbMATH Open document ID: 1204.68182
author: Michael Bauland
author: Elmar Böhler
author: Nadia Creignou
author: S. Reith
author: Henning Schnoor
author: Heribert Vollmer
published in: Theory of Computing Systems
publication date: 2010-10-06T00:00:00Z
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5796560
zbMATH Keywords: satisfiability problems
zbMATH Keywords: quantified formulas
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: s00224-009-9194-6
OpenAlex ID: W2000423606
cites work: Mathematical Foundations of Computer Science 2005
cites work: Theory and Applications of Satisfiability Testing
cites work: Q4411838
cites work: Bases for Boolean co-clones
cites work: Computer Science Logic
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: Towards a dichotomy theorem for the counting constraint satisfaction problem
cites work: The complexity of theorem-proving procedures
cites work: Complexity of generalized satisfiability counting problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Complexity of constraints. An overview of current research themes
cites work: Subtractive reductions and complete problems for counting complexity classes
cites work: Closure properties of constraints
cites work: Q4488342
cites work: Polynomial Space Counting Problems
cites work: Function Algebras on Finite Sets
cites work: Q4071737
cites work: Q4298260
cites work: Q4354427
cites work: The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
cites work: Undirected ST-connectivity in log-space
cites work: The complexity of satisfiability problems
cites work: Partial Polymorphisms and Constraint Satisfaction Problems
cites work: The polynomial-time hierarchy
cites work: Q4131648
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
cites work: The complexity of computing the permanent
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Complete sets and the polynomial-time hierarchy
cites work: #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
DOI: 10.1007/S00224-009-9194-6
Recommended article: Computer Science Logic
Recommended article: The Complexity of Quantified Constraints Using the Algebraic Formulation
Recommended article: The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
Recommended article: Q4525271
Recommended article: Complexity of combinations of qualitative constraint satisfaction problems
Recommended article: Quantified Constraints and Containment Problems
Recommended article: Q5109509
Recommended article: The complexity of constraint satisfaction revisited
Recommended article: Complexity and approximability of quantified and stochastic constraint satisfaction problems
Recommended article: Classifying the Complexity of Constraints Using Finite Algebras
description: scientific article; zbMATH DE number 5796560