Complexity and approximability of quantified and stochastic constraint satisfaction problems

MaRDI QIDQ2741527zbMATH OpenFDO

Authors R. E. Stearns, H. B. III Hunt, Madhav V. Marathe

Publication date 24 September 2001

zbMATH Keywords

complexityefficient approximability

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Stochastic programming (90C15) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The complexity of problems for quantified constraints
• Computer Science Logic
• STACS 2005
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• A dichotomy theorem for maximum generalized satisfiability problems.

Cites work

• scientific article; zbMATH DE number 42044 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1332658 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• A dichotomy theorem for maximum generalized satisfiability problems.
• Algebraic Structures with Hard Equivalence and Minimization Problems
• Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
• Approximation algorithms for NP-hard problems.
• Bandwidth contrained NP-complete problems
• Building tractable disjunctive constraints
• Closure properties of constraints
• Complete problems for space bounded subclasses of NP
• Complexity of problems in games, graphs and algebraic equations
• Efficient solutions of hierarchical systems of linear equations
• Games against nature
• Monotone monadic SNP and constraint satisfaction
• On Unapproximable Versions of NP-Complete Problems
• Optimization complexity of linear logic proof games
• Optimization, approximation, and complexity classes
• Planar Formulae and Their Uses
• Polynomial Space Counting Problems
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Proof verification and the hardness of approximation problems
• Quantifiers and approximation
• Random Debaters and the Hardness of Approximating Stochastic Functions
• Stochastic Boolean satisfiability
• Strongly-local reductions and the complexity/efficient approximability of algebra and optimization on abstract algebraic structures
• The complexity of optimization problems
• The complexity of satisfiability problems
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems

Cited in

(6)

• Logic Programming and Nonmonotonic Reasoning
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• PTAS for Sparse General-valued CSPs
• Confidence-based reasoning in stochastic constraint programming
• On the complexity of trial and error for constraint satisfaction problems
• The complexity of problems for quantified constraints

This page was built for publication: Complexity and approximability of quantified and stochastic constraint satisfaction problems

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