Graduate studies at Western
Journal of Symbolic Logic 59 (1):73-86 (1994)
|Abstract||LK is a natural modification of Gentzen sequent calculus for propositional logic with connectives ¬ and $\bigwedge, \bigvee$ (both of bounded arity). Then for every d ≥ 0 and n ≥ 2, there is a set Td n of depth d sequents of total size O(n3 + d) which are refutable in LK by depth d + 1 proof of size exp(O(log2 n)) but such that every depth d refutation must have the size at least exp(nΩ(1)). The sets Td n express a weaker form of the pigeonhole principle|
|Keywords||Lengths of proofs propositional calculus Frege systems pigeonhole principle|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Jan Krajíček (2005). Structured Pigeonhole Principle, Search Problems and Hard Tautologies. Journal of Symbolic Logic 70 (2):619 - 630.
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.
Jan Krajíček (1995). Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press.
Samuel R. Buss (1987). Polynomial Size Proofs of the Propositional Pigeonhole Principle. Journal of Symbolic Logic 52 (4):916-927.
Jan Krajíček (2004). Implicit Proofs. Journal of Symbolic Logic 69 (2):387 - 397.
Maria Bonet, Toniann Pitassi & Ran Raz (1997). Lower Bounds for Cutting Planes Proofs with Small Coefficients. Journal of Symbolic Logic 62 (3):708-728.
A. Carbone (2002). The Cost of a Cycle is a Square. Journal of Symbolic Logic 67 (1):35-60.
Nathan Segerlind (2007). The Complexity of Propositional Proofs. Bulletin of Symbolic Logic 13 (4):417-481.
Pavel Hrubeš (2007). Lower Bounds for Modal Logics. Journal of Symbolic Logic 72 (3):941 - 958.
Jan Krajicek (1994). Lower Bounds to the Size of Constant-Depth Propositional Proofs. Journal of Symbolic Logic 59 (1):73 - 86.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Recent downloads (6 months)0
How can I increase my downloads?