Complexity of counting the optimal solutions

DOI10.1016/j.tcs.2009.05.025zbMath1171.68011OpenAlexW1980428853MaRDI QIDQ837174

Reinhard Pichler, Miki Hermann

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.025

zbMATH Keywords

computational complexityoptimization problemscounting complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ Counting complexity of propositional abduction ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Computing functions with parallel queries to NP
• The complexity of optimization problems
• On counting and approximation
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Generalizations of Opt P to the polynomial hierarchy
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• The complexity of propositional closed world reasoning and circumscription
• Complexity of generalized satisfiability counting problems
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Subtractive reductions and complete problems for counting complexity classes
• Positive Relativizations of Complexity Classes
• Bounded Query Classes
• The Complexity of Enumeration and Reliability Problems
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• The complexity of satisfiability problems
• The Complexity of Counting Functions with Easy Decision Version

This page was built for publication: Complexity of counting the optimal solutions