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

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

Abstract

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

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,779

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

Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds.Jan Kraj�?Ek - 2004 - Journal of Symbolic Logic 69 (1):265-286.
Structured Pigeonhole Principle, Search Problems and Hard Tautologies.Jan Krajíček - 2005 - Journal of Symbolic Logic 70 (2):619 - 630.
Resolution over linear equations and multilinear proofs.Ran Raz & Iddo Tzameret - 2008 - Annals of Pure and Applied Logic 155 (3):194-224.
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Lower Bounds for Modal Logics.Pavel Hrubeš - 2007 - Journal of Symbolic Logic 72 (3):941 - 958.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
Structured pigeonhole principle, search problems and hard tautologies.Jan Krajíček - 2005 - Journal of Symbolic Logic 70 (2):619-630.
The weak pigeonhole principle for function classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
On the Existence of Strong Proof Complexity Generators.Jan Krajíček - 2024 - Bulletin of Symbolic Logic 30 (1):20-40.
Interpolation theorems, lower Bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.

Analytics

Added to PP
2009-02-05

Downloads
29 (#537,165)

6 months
7 (#592,867)

Historical graph of downloads
How can I increase my downloads?

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.
Towards NP – P via proof complexity and search.Samuel R. Buss - 2012 - Annals of Pure and Applied Logic 163 (7):906-917.

View all 6 citations / Add more citations

References found in this work

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.

Add more references