Complexity of Counting the Optimal Solutions

DOI10.1007/978-3-540-69733-6_16MaRDI QIDQ3511323zbMATH OpenOpenAlexFDO

Authors Miki Hermann, Reinhard Pichler

Publication date 10 July 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69733-6_16

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Complexity of counting the optimal solutions
• Complexity classes defined by counting quantifiers
• Polynomial-time hierarchies on some classes of functions. I
• The complexity of optimization problems

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1072530 (Why is no real title available?)
• scientific article; zbMATH DE number 809154 (Why is no real title available?)
• Bounded Query Classes
• Complete sets and the polynomial-time hierarchy
• Complexity of generalized satisfiability counting problems
• Computing functions with parallel queries to NP
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Generalizations of Opt P to the polynomial hierarchy
• On counting and approximation
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Positive Relativizations of Complexity Classes
• Subtractive reductions and complete problems for counting complexity classes
• The Complexity of Counting Functions with Easy Decision Version
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• The complexity of optimization problems
• The complexity of propositional closed world reasoning and circumscription

Cited in

(7)

• Relation between the hardness of a problem and the number of its solutions
• Complexity of counting the optimal solutions
• A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
• Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
• ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
• Approximately Counting Locally-Optimal Structures
• scientific article; zbMATH DE number 176749 (Why is no real title available?)

This page was built for publication: Complexity of Counting the Optimal Solutions

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