Complexity of counting the optimal solutions

DOI10.1016/J.TCS.2009.05.025MaRDI QIDQ837174zbMATH OpenOpenAlexFDO

Authors Miki Hermann, Reinhard Pichler

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 complexitycounting complexityoptimization problems

Mathematics Subject Classification ID

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

Recommendations

• Complexity of Counting the Optimal Solutions
• Complexity classes defined by counting quantifiers
• The relative complexity of approximate counting problems

Cites work

• 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
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 612169 (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?)
• On counting and approximation
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Positive Relativizations of Complexity Classes
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Subtractive reductions and complete problems for counting complexity classes
• The complexity of computing the permanent
• The Complexity of Counting Functions with Easy Decision Version
• The Complexity of Enumeration and Reliability Problems
• The complexity of optimization problems
• The complexity of propositional closed world reasoning and circumscription
• The complexity of satisfiability problems
• The polynomial-time hierarchy

Cited in

(9)

• A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Approximately Counting Locally-Optimal Structures
• Complexity of Counting the Optimal Solutions
• Complexity of counting feedback vertex sets
• Relation between the hardness of a problem and the number of its solutions
• Counting and enumeration complexity with application to multicriteria scheduling
• New perspectives on semiring applications to dynamic programming
• Counting complexity of propositional abduction

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 Q837174)