Approximate Counting in Bounded Arithmetic

Journal of Symbolic Logic 72 (3):959 - 993 (2007)
  Copy   BIBTEX

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 PV₁ + dWPHP(PV)

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1191333850

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,122

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Approximate counting by hashing in bounded arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Finite automata, real time processes and counting problems in bounded arithmetics.Mirosław Kutyłowski - 1988 - Journal of Symbolic Logic 53 (1):243-258.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Exact and Approximate Arithmetic in an Amazonian Indigene Group.Pierre Pica, Cathy Lemer, Véronique Izard & Stanislas Dehaene - 2004 - Science 306 (5695):499-503.
On interpretations of bounded arithmetic and bounded set theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
Regularity in models of arithmetic.George Mills & Jeff Paris - 1984 - Journal of Symbolic Logic 49 (1):272-280.
On the Herbrand Notion of Consistency for Finitely Axiomatizable Fragments of Bounded Arithmetic Theories.Leszek Aleksander Kołodziejczyk - 2006 - Journal of Symbolic Logic 71 (2):624 - 638.
Could experience disconfirm the propositions of arithmetic?Jessica M. Wilson - 2000 - Canadian Journal of Philosophy 30 (1):55--84.
Symbolic arithmetic knowledge without instruction.Camilla K. Gilmore, Shannon E. McCarthy & Elizabeth S. Spelke - unknown
Finite reverse mathematics.Harvey Friedman - manuscript
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
Children’s understanding of the relationship between addition and subtraction.Elizabeth Spelke & Camilla Gilmore - 2008 - Cognition 107 (3):932-945.

Analytics

Added to PP
2010-08-24

Downloads
205 (#92,849)

6 months
9 (#210,105)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Feasibly constructive proofs of succinct weak circuit lower bounds.Moritz Müller & Ján Pich - 2020 - Annals of Pure and Applied Logic 171 (2):102735.
Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
Circuit lower bounds in bounded arithmetics.Ján Pich - 2015 - Annals of Pure and Applied Logic 166 (1):29-45.
Uniform proofs of ACC representations.Sam Buss - 2017 - Archive for Mathematical Logic 56 (5-6):639-669.

View all 7 citations / Add more citations

References found in this work

Bounded arithmetic and the polynomial hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Dual weak pigeonhole principle, Boolean complexity, and derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
Structures interpretable in models of bounded arithmetic.Neil Thapen - 2005 - Annals of Pure and Applied Logic 136 (3):247-266.

Add more references