On the Relative Complexity of Approximate Counting Problems
Authors:
- 1 January 2000
- book chapter
- Published by Springer Nature
- p. 108-119
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- On the Relative Complexity of Approximate Counting Problems2000
- On the hardness of approximate reasoningArtificial Intelligence, 1996
- Descriptive Complexity of #P FunctionsJournal of Computer and System Sciences, 1995
- PP is as Hard as the Polynomial-Time HierarchySIAM Journal on Computing, 1991
- Monte-Carlo approximation algorithms for enumeration problemsJournal of Algorithms, 1989
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is ConnectedSIAM Journal on Computing, 1983
- The complexity of approximate counting1983
- On the difference between one and many1977