Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-24T14:02:29.570Z Has data issue: false hasContentIssue false
  • English
  • Français

Approximate counting in bounded arithmetic

Published online by Cambridge University Press:  12 March 2014

Emil Jeřábek
Emil Jeřábek*
Affiliation:
Institute of Mathematics, AS CR, Žitná 25, 115 67 Praha 1, Czech Republic. E-mail: [email protected], URL: http://math.cas.cz/~jerabek/index.html
Get access Rights & Permissions [Opens in a new window]

Abstract

We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV1 + dWPHP(PV).

Keywords

Bounded arithmeticpigeonhole principlecountingrandomized algorithms
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 3 , September 2007 , pp. 959 - 993
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Babai, László, Trading group theory for randomness, Proceedings of the ACM Symposium on Theory of Computing, 1985, pp. 421–429.Google Scholar
[2]Babai, László and Moran, Shlomo, Arthur–Merlin games: A randomized proof system, and a hierarchy of complexity classes, Journal of Computer and System Sciences, vol. 36 (1988), no. 2, pp. 254–276.CrossRefGoogle Scholar
[3]Bennett, Charles H. and Gill, John, Relative to a random oracle A, PA ≠ NPA ≠ co-NPA with probability 1, SIAM Journal on Computing, vol. 10 (1981), no. 1, pp. 96–113.CrossRefGoogle Scholar
[4]Bishop, Errett and Bridges, Douglas S., Constructive Analysis, Grundlehren der mathematischen Wissenschaften, vol. 279, Springer, 1985.CrossRefGoogle Scholar
[5]Bovet, Daniel P., Crescenzi, Pierluigi, and Silvestri, Riccardo, A uniform approach to define complexity classes, Theoretical Computer Science, vol. 104 (1992), no. 2, pp. 263–283.CrossRefGoogle Scholar
[6]Buss, Samuel R., Bounded Arithmetic, Bibliopolis, Naples, 1986.Google Scholar
[7]Buss, Samuel R., Relating the bounded arithmetic and polynomial time hierarchies, Annals of Pure and Applied Logic, vol. 75 (1995), no. 1–2, pp. 67–77.CrossRefGoogle Scholar
[8]Buss, Samuel R., First-order proof theory of arithmetic, Handbook of Proof Theory (Buss, Samuel R., editor), Studies in Logic and the Foundations of Mathematics, vol. 137, Elsevier, Amsterdam, 1998, pp. 79–147.CrossRefGoogle Scholar
[9]Cook, Stephen A., Feasibly constructive proofs and the propositional calculus, Proceedings of the ACM Symposium on Theory of Computing, ACM, 1975, pp. 83–97.Google Scholar
[10]Cook, Stephen A., Relating the provable collapse of P to NC1 and the power of logical theories, Proof Complexity and Feasible Arithmetics (Bearne, Paul and Buss, Samuel R., editors), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 39, American Mathematical Society, 1998, pp. 73–92.CrossRefGoogle Scholar
[11]Cook, Stephen A., Theories for complexity classes and their propositional translations, Complexity of Computations and Proofs (Krajíček, Jan, editor), Quaderni di Matematica, vol. 13, Seconda Universita di Napoli, 2004. pp. 175–227.Google Scholar
[12]Gill, John, Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, vol. 6 (1977), no. 4, pp. 675–695.CrossRefGoogle Scholar
[13]Hájek, Petr and Pudlák, Pavel, Metamathematics of First-Order Arithmetic, Perspectives in Mathematical Logic, Springer, 1993, second edition 1998.CrossRefGoogle Scholar
[14]Hartmanis, Juris and Hemachandra, Lane A., Complexity classes without machines: On complete languages for UP, Theoretical Computer Science, vol. 58 (1988), pp. 129–142.CrossRefGoogle Scholar
[15]Jeřábek, Emil, Dual weak pigeonhole principle, Boolean complexity, and derandomization, Annals of Pure and Applied Logic, vol. 129 (2004). pp. 1–37.CrossRefGoogle Scholar
[16]Jeřábek, Emil, The strength of sharply bounded induction, Mathematical Logic Quarterly, vol. 52 (2006), no. 6, pp. 613–624.CrossRefGoogle Scholar
[17]Jeřábek, Emil, On independence of variants of the weak pigeonhole principle, submitted, 2006.Google Scholar
[18]Kabanets, Valentine, Rackoff, Charles, and Cook, Stephen A., Efficiently approximable real-valued functions, Technical Report TR00-034, Electronic Colloquium on Computational Complexity, 2000.Google Scholar
[19]Krajíček, Jan, Bounded arithmetic, propositional logic, and complexity theory, Encyclopedia of Mathematics and Its Applications, vol. 60, Cambridge University Press, 1995.CrossRefGoogle Scholar
[20]Krajíček, Jan, Pudlák, Pavel, and Takeuti, Gaisi, Bounded arithmetic and the polynomial hierarchy, Annals of Pure and Applied Logic, vol. 52 (1991), no. 1-2, pp. 143–153.CrossRefGoogle Scholar
[21]Lautemann, Clemens, BPP and the polynomial hierarchy, Information Processing Letters, vol. 17 (1983), no. 4, pp. 215–217.CrossRefGoogle Scholar
[22]Maciel, Alexis, Pitassi, Toniann, and Woods, Alan R., A new proof of the weak pigeonhole principle, Journal of Computer and System Sciences, vol. 64 (2002). no. 4, pp. 843–872.CrossRefGoogle Scholar
[23]Nisan, Noam and Wigderson, Avi, Hardness vs. randomness, Journal of Computer and System Sciences, vol. 49 (1994). no. 2, pp. 149–167.CrossRefGoogle Scholar
[24]Paris, Jeff B., Wilkie, Alex J., and Woods, Alan R., Provability of the pigeonhole principle and the existence of infinitely many primes, this Journal, vol. 53 (1988), no. 4, pp. 1235–1244.Google Scholar
[25]Riis, Søren M., Making infinite structures finite in models of second order bounded arithmetic, Arithmetic, proof theory, and computational complexity (Clote, Peter and Krajíček, Jan, editors), Oxford Logic Guides, vol. 23, Oxford University Press, 1993, pp. 289–319.Google Scholar
[26]Sipser, Michael, A complexity theoretic approach to randomness, Proceedings of the ACM Symposium on Theory of Computing, ACM, 1983, pp. 330–335.Google Scholar
[27]Thapen, Neil, The weak pigeonhole principle in models of bounded arithmetic, Ph.D. thesis, Oxford University, 2002.Google Scholar
[28]Thapen, Neil, Structures interpretahle in models of bounded arithmetic, Annals of Pure and Applied Logic, vol. 136 (2005), no. 3, pp. 247–266.CrossRefGoogle Scholar