Complexity of counting the optimal solutions
From MaRDI portal
Publication:837174
DOI10.1016/J.TCS.2009.05.025zbMATH Open1171.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
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of optimization problems
- The complexity of computing the permanent
- The Complexity of Enumeration and Reliability Problems
- The complexity of satisfiability problems
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Complexity of generalized satisfiability counting problems
- Subtractive reductions and complete problems for counting complexity classes
- The polynomial-time hierarchy
- Bounded Query Classes
- Computing functions with parallel queries to NP
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- On counting and approximation
- Complete sets and the polynomial-time hierarchy
- The complexity of propositional closed world reasoning and circumscription
- Positive Relativizations of Complexity Classes
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Generalizations of Opt P to the polynomial hierarchy
- The Complexity of Counting Functions with Easy Decision Version
Cited In (5)
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)
