Complexity of Counting the Optimal Solutions

DOI10.1007/978-3-540-69733-6_16zbMath1148.68381OpenAlexW2247609287MaRDI QIDQ3511323

Reinhard Pichler, Miki Hermann

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)

Related Items (1)

Counting Complexity of Minimal Cardinality and Minimal Weight Abduction

Cites Work

• 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
• Complete sets and the polynomial-time hierarchy
• The complexity of propositional closed world reasoning and circumscription
• Complexity of generalized satisfiability counting problems
• 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 Counting Functions with Easy Decision Version
• Unnamed Item
• Unnamed Item
• Unnamed Item

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