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 has no associated abstract. (fix it) | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,653 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesJan Krajíček (2004). Dual Weak Pigeonhole Principle, Pseudo-Surjective Functions, and Provability of Circuit Lower Bounds. Journal of Symbolic Logic 69 (1):265 - 286.
Jan Krajíček (1997). Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic. Journal of Symbolic Logic 62 (2):457-486.
Samuel R. Buss (1987). Polynomial Size Proofs of the Propositional Pigeonhole Principle. Journal of Symbolic Logic 52 (4):916-927.
Andreas Blass (1995). An Induction Principle and Pigeonhole Principles for K-Finite Sets. Journal of Symbolic Logic 60 (4):1186-1193.
Jan Krajíček (2004). Approximate Euler Characteristic, Dimension, and Weak Pigeonhole Principles. Journal of Symbolic Logic 69 (1):201 - 214.
Juris Steprāns (2005). Geometric Cardinal Invariants, Maximal Functions and a Measure Theoretic Pigeonhole Principle. Bulletin of Symbolic Logic 11 (4):517-525.
J. B. Paris, A. J. Wilkie & A. R. Woods (1988). Provability of the Pigeonhole Principle and the Existence of Infinitely Many Primes. Journal of Symbolic Logic 53 (4):1235-1244.
Mario Chiari & Jan Krajíček (1998). Witnessing Functions in Bounded Arithmetic and Search Problems. Journal of Symbolic Logic 63 (3):1095-1115.
Jan Kraj�?Ek (2004). Approximate Euler Characteristic, Dimension, and Weak Pigeonhole Principles. Journal of Symbolic Logic 69 (1):201-214.
Jan Krajiček (1994). Lower Bounds to the Size of Constant-Depth Propositional Proofs. Journal of Symbolic Logic 59 (1):73-86.
J. C. E. Dekker & E. Ellentuck (1989). Isols and the Pigeonhole Principle. Journal of Symbolic Logic 54 (3):833-846.
Jared R. Corduan & François G. Dorais (2012). On the Indecomposability of $\Omega^{N}$. Notre Dame Journal of Formal Logic 53 (3):373-395.
Leszek Aleksander Kołodziejczyk & Neil Thapen (2008). The Polynomial and Linear Hierarchies in Models Where the Weak Pigeonhole Principle Fails. Journal of Symbolic Logic 73 (2):578-592.
Jason Aubrey (2004). Combinatorics for the Dominating and Unsplitting Numbers. Journal of Symbolic Logic 69 (2):482 - 498.
Pavel Pudlák (1997). Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations. Journal of Symbolic Logic 62 (3):981-998.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2010-08-24Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
