|
 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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
L. Adleman, Two theorems on random polynomial time, Proc. 19th Annual IEEE Symp. on Foundations of Computer Science, 1978, 75-83.
|
| |
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.
|
 |
5
|
|
| |
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.
|
| |
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.
|
| |
10
|
|
| |
11
|
J. Gill, Computational complexity of probabilistic Turing machines, SIAM J. Comput. 6 (1977), 675-695.
|
| |
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
|
Udi Manber , Martin Tompa, Probabilistic, nondeterministic, and alternating decision trees (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.234-244, May 05-07, 1982, San Francisco, California, United States
[doi> 10.1145/800070.802197]
|
| |
17
|
M. O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), 273-280.
|
| |
18
|
|
| |
19
|
|
| |
20
|
R. Solovay and V. Strassen, A fast monte-carlo test for primality, SIAM J. Comput. 6 (1977), 84-85.
|
| |
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.
|
CITED BY 17
|
|
R M Karp , E Upfal , A Wigderson, Are search and decision programs computationally equivalent?, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.464-475, May 06-08, 1985, Providence, Rhode Island, United States
|
|
|
|
|
|
|
|
|
Ziv Bar-Yosseff , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
William Aiello , Mihir Bellare , Ramarathnam Venkatesan, Knowledge on the average—perfect, statistical and logarithmic, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.469-478, May 29-June 01, 1995, Las Vegas, Nevada, United States
|
|
|
Oded Goldreich , Rafail Ostrovsky , Erez Petrank, Computational complexity and knowledge complexity (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.534-543, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
S. Ben-David , B. Chor , O. Goldreich, On the theory of average case complexity, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.204-216, May 14-17, 1989, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.2