Annals of Pure and Applied Logic 129 (1-3):1-37 (2004)

Authors
Abstract
We study the extension 123) of the theory S21 by instances of the dual weak pigeonhole principle for p-time functions, dWPHPx2x. We propose a natural framework for formalization of randomized algorithms in bounded arithmetic, and use it to provide a strengthening of Wilkie's witnessing theorem for S21+dWPHP. We construct a propositional proof system WF , which captures the Π1b-consequences of S21+dWPHP. We also show that WF p-simulates the Unstructured Extended Nullstellensatz proof system of Buss et al. 256). We prove that dWPHP is equivalent to a statement asserting the existence of a family of Boolean functions with exponential circuit complexity. Building on this result, we formalize the Nisan–Wigderson construction in a conservative extension of S21+dWPHP
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2003.12.003
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 54,385
Through your library

References found in this work BETA

Existence and Feasibility in Arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
Quantified Propositional Calculi and Fragments of Bounded Arithmetic.Jan Krajíček & Pavel Pudlák - 1990 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 36 (1):29-46.

Add more references

Citations of this work BETA

Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.

View all 13 citations / Add more citations

Similar books and articles

Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
The Weak Pigeonhole Principle for Function Classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
Monotone Proofs of the Pigeon Hole Principle.R. Gavalda, A. Atserias & N. Galesi - 2001 - Mathematical Logic Quarterly 47 (4):461-474.
Abelian Groups and Quadratic Residues in Weak Arithmetic.Emil Jeřábek - 2010 - Mathematical Logic Quarterly 56 (3):262-278.
Isols and the Pigeonhole Principle.J. C. E. Dekker & E. Ellentuck - 1989 - Journal of Symbolic Logic 54 (3):833-846.
A Model-Theoretic Characterization of the Weak Pigeonhole Principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
On the Indecomposability of $\Omega^{N}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.
Degree Complexity for a Modified Pigeonhole Principle.Maria Luisa Bonet & Nicola Galesi - 2003 - Archive for Mathematical Logic 42 (5):403-414.

Analytics

Added to PP index
2014-01-16

Total views
13 ( #700,702 of 2,362,053 )

Recent downloads (6 months)
1 ( #553,136 of 2,362,053 )

How can I increase my downloads?

Downloads

My notes