Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds

Journal of Symbolic Logic 69 (1):265-286 (2004)

This article is a continuation of our search for tautologies that are hard even for strong propositional proof systems like EF, cf. [Kra-wphp,Kra-tau]. The particular tautologies we study, the τ-formulas, are obtained from any
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI http://projecteuclid.org/euclid.jsl/1080938841
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

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

References found in this work BETA

On Theories of Bounded Arithmetic for NC 1.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):322-340.
Tautologies From Pseudo-Random Generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
Tautologies From Pseudo-Random Generators, By, Pages 197 -- 212.Jan Krajicek - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.

Add more references

Citations of this work BETA

Towards NP – P Via Proof Complexity and Search.Samuel R. Buss - 2012 - Annals of Pure and Applied Logic 163 (7):906-917.

Add more citations

Similar books and articles

The Weak Pigeonhole Principle for Function Classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
Dual Weak Pigeonhole Principle, Boolean Complexity, and Derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
Resolution Over Linear Equations and Multilinear Proofs.Ran Raz & Iddo Tzameret - 2008 - Annals of Pure and Applied Logic 155 (3):194-224.
Pigeonhole and Choice Principles.Wolfgang Degen - 2000 - Mathematical Logic Quarterly 46 (3):313-334.
Upper and Lower Ramsey Bounds in Bounded Arithmetic.Kerry Ojakian - 2005 - Annals of Pure and Applied Logic 135 (1-3):135-150.
Structures Interpretable in Models of Bounded Arithmetic.Neil Thapen - 2005 - Annals of Pure and Applied Logic 136 (3):247-266.


Added to PP index

Total views
196 ( #37,142 of 2,266,272 )

Recent downloads (6 months)
17 ( #46,523 of 2,266,272 )

How can I increase my downloads?


My notes

Sign in to use this feature