Article

Free access

The complexity of approximate counting

Author:

Larry StockmeyerAuthors Info & Claims

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

Pages 118 - 126

https://doi.org/10.1145/800061.808740

Published: 01 December 1983 Publication History

Abstract

There are several computational problems that can be formulated as problems of counting the number of objects having a certain property. Valiant [22] has introduced the class #P which includes a variety of counting problems such as counting the number of perfect matchings in a graph, computing the permanent of a matrix [22], finding the size of a backtrack search tree [14], and computing the probability that a network remains connected when links can fail with a certain probability [23].

We define and study a class of restricted, but very natural, probabilistic sampling methods motivated by the particular counting problems mentioned above. Instead of “singleton sampling” the algorithm is allowed to sample a large set S ample; U in one step; the information returned from the sample is whether S contains any element having the property being counted.

We attempt to classify the complexity of computing approximate solutions to problems in #P. The classification is done in terms of the polynomial-time hierarchy (for short, P-hierarchy) [21].

We give a relativization result that complements a recent result of Sipser and Gaacute;c [19] that BPP is contained in the second level of the P-hierarchy.

References

[1]

L. Adleman, Two theorems on random polynomial time, Proc. 19th Annual IEEE Symp. on Foundations of Computer Science, 1978, 75-83.

Digital Library

[2]

D. Angluin, On counting problems and the polynomial time hierarchy, Theoretical Computer Science 12 (1980), 161-173.

[3]

D. Angluin and L. G. Valiant, Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. Comput. Syst. Sci. 18 (1979), 155-193.

[4]

T. Baker, J. Gill, and R. Solovay, Relativizations of the P &equil;? NP question, SIAM J. Comput. 4 (1975), 431-442.

Digital Library

[5]

A. K. Chandra, S. Fortune, and R. J. Lipton, Unbounded fan-in circuits and associative functions, Proc. 15th ACM Symp. on Theory of Computing, 1983.

Digital Library

[6]

A. K. Chandra, L. J. Stockmeyer, and U. Vishkin, A complexity theory for unbounded fan-in parallelism, Proc. 23rd Annual IEEE Symp. on Foundations of Computer Science, 1982, 1-13.

Digital Library

[7]

P. Erdös and J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, New York, 1974.

[8]

R. V. Freivald, Fast computation by probabilistic Turing machines, Theory of Algorithms and Programs 2 (1975), 201-205 (in Russian).

[9]

M. Furst, J. B. Saxe, and M. Sipser, Parity, circuits and the polynomial time hierarchy, Proc. 22nd IEEE Symp. on Foundations of Computer Science, 1981, 260-270.

Digital Library

[10]

M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979.

Digital Library

[11]

J. Gill, Computational complexity of probabilistic Turing machines, SIAM J. Comput. 6 (1977), 675-695.

Digital Library

[12]

L. M. Goldschlager, An approximation algorithm for computing the permanent, typescript, Dept. of Computer Science, University of Queensland, Queensland, Australia.

[13]

R. Karp, personal communication.

[14]

D. E. Knuth, Estimating the efficiency of backtrack programs Math. of Computation 29 (1975), 121-136.

[15]

E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.

[16]

U. Manber and M. Tompa, Probabilistic, nondeterministic, and alternating decision trees, Proc. 14th ACM Symp. on Theory of Computing, 1982, 234-244.

Digital Library

[17]

M. O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), 273-280.

Digital Library

[18]

M. Sipser, Borel sets and circuit complexity, Proc. 15th ACM Symp. on Theory of Computing, 1983.

Digital Library

[19]

M. Sipser, A complexity theoretic approach to randomness, Proc. 15th ACM Symp. on Theory of Computing, 1983.

Digital Library

[20]

R. Solovay and V. Strassen, A fast monte-carlo test for primality, SIAM J. Comput. 6 (1977), 84-85.

Digital Library

[21]

L. J. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science 3 (1977), 1-22.

[22]

L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8 (1979), 189-201.

[23]

L. G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979), 410-421.

Digital Library

Cited By

Baranov EChakraborty SLegay AMeel KVinodchandran N(2024)A Scalable t-Wise Coverage Estimator: Algorithms and ApplicationsIEEE Transactions on Software Engineering10.1109/TSE.2024.341991950:8(2021-2039)Online publication date: Aug-2024
https://doi.org/10.1109/TSE.2024.3419919
Dalzell AHunter-Jones NBrandão F(2024)Random Quantum Circuits Transform Local Noise into Global White NoiseCommunications in Mathematical Physics10.1007/s00220-024-04958-z405:3Online publication date: 12-Mar-2024
https://doi.org/10.1007/s00220-024-04958-z
Hirahara SLu ZRen H(2023)Bounded RelativizationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.6(1-45)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.6
Show More Cited By

Index Terms

The complexity of approximate counting
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness
  2. Models of computation
    1. Probabilistic computation

Recommendations

Pseudorandomness for Approximate Counting and Sampling

We study computational procedures that use both randomness and nondeterminism. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to "boost" a given hardness ...
Pseudorandomness for Approximate Counting and Sampling
CCC '05: Proceedings of the 20th Annual IEEE Conference on Computational Complexity

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible ...
The Complexity of Planar Counting Problems

We prove the #P-hardness of the counting problems associated with various satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing

December 1983

487 pages

ISBN:0897910990

DOI:10.1145/800061

Copyright © 1983 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

127
Total Citations
View Citations
1,278
Total Downloads

Downloads (Last 12 months)475
Downloads (Last 6 weeks)55

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Baranov EChakraborty SLegay AMeel KVinodchandran N(2024)A Scalable t-Wise Coverage Estimator: Algorithms and ApplicationsIEEE Transactions on Software Engineering10.1109/TSE.2024.341991950:8(2021-2039)Online publication date: Aug-2024
https://doi.org/10.1109/TSE.2024.3419919
Dalzell AHunter-Jones NBrandão F(2024)Random Quantum Circuits Transform Local Noise into Global White NoiseCommunications in Mathematical Physics10.1007/s00220-024-04958-z405:3Online publication date: 12-Mar-2024
https://doi.org/10.1007/s00220-024-04958-z
Hirahara SLu ZRen H(2023)Bounded RelativizationProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.6(1-45)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.6
Wu YWu BWang JYuan X(2023)Quantum Phase Recognition via Quantum Kernel MethodsQuantum10.22331/q-2023-04-17-9817(981)Online publication date: 17-Apr-2023
https://doi.org/10.22331/q-2023-04-17-981
Lai YMeel KYap RWilliams BChen YNeville J(2023)Fast converging anytime model countingProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i4.25517(4025-4034)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i4.25517
Woodruff D(2023)Technical Perspective: Tapping the Link between Algorithmic Model Counting and StreamingCommunications of the ACM10.1145/360782566:9(94-94)Online publication date: 23-Aug-2023
https://dl.acm.org/doi/10.1145/3607825
Pavan AVinodchandran NBhattacharyya AMeel K(2023)Model Counting Meets Distinct ElementsCommunications of the ACM10.1145/360782466:9(95-102)Online publication date: 23-Aug-2023
https://dl.acm.org/doi/10.1145/3607824
Pavan AVinodchandran NBhattacharyya AMeel K(2023)Model Counting Meets F0 EstimationACM Transactions on Database Systems10.1145/360349648:3(1-28)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.1145/3603496
Hangleiter DEisert J(2023)Computational advantage of quantum random samplingReviews of Modern Physics10.1103/RevModPhys.95.03500195:3Online publication date: 20-Jul-2023
https://doi.org/10.1103/RevModPhys.95.035001
Bishnu AGhosh AKolay SMishra GSaurabh S(2023)Almost optimal query algorithm for hitting set using a subset queryJournal of Computer and System Sciences10.1016/j.jcss.2023.02.002137(50-65)Online publication date: Nov-2023
https://doi.org/10.1016/j.jcss.2023.02.002
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents