- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
Journal of Symbolic Logic 69 (1):265-286 (2004)
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 anyLinks
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
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.
Resolution over linear equations and multilinear proofs.Ran Raz & Iddo Tzameret - 2008 - Annals of Pure and Applied Logic 155 (3):194-224.
Structured Pigeonhole Principle, Search Problems and Hard Tautologies.Jan Krajíček - 2005 - Journal of Symbolic Logic 70 (2):619 - 630.
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.
Tautologies from pseudo-random generators.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
The weak pigeonhole principle for function classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
Reasoning processes in propositional logic.Claes Strannegård, Simon Ulfsbäcker, David Hedqvist & Tommy Gärling - 2010 - Journal of Logic, Language and Information 19 (3):283-314.
Analytics
Added to PP
2009-02-05
Downloads
208 (#100,361)
6 months
7 (#491,177)
2009-02-05
Downloads
208 (#100,361)
6 months
7 (#491,177)
Historical graph of 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.
On the proof complexity of the nisan–wigderson generator based on a hard np ∩ conp function.Jan Krajíček - 2011 - Journal of Mathematical Logic 11 (1):11-27.
On the correspondence between arithmetic theories and propositional proof systems – a survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.
Information in propositional proofs and algorithmic proof search.Jan Krajíček - 2022 - Journal of Symbolic Logic 87 (2):852-869.
Hardness assumptions in the foundations of theoretical computer science.Jan Krajíček - 2005 - Archive for Mathematical Logic 44 (6):667-675.
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.
Tautologies From Pseudo-random Generators, By, Pages 197 -- 212.Jan Krajíček - 2001 - Bulletin of Symbolic Logic 7 (2):197-212.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-68866f4b87-zhzfn uwo