Complexity of Counting the Optimal Solutions
From MaRDI portal
Publication:3511323
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
Related Items (1)
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