Publication:4850545
From MaRDI portal
zbMath0834.03021MaRDI QIDQ4850545
Toniann Pitassi, Maria Luisa Bonet, Samuel R. Buss
Publication date: 17 October 1995
Kruskal-Katona theorem; extended Frege systems; speed-up; pigeonhole principle; combinatorial tautologies; Bondy's theorem; extended Frege proofs; polynomial-size
03F20: Complexity of proofs
Related Items
Characterizing Propositional Proofs as Noncommutative Formulas, Short Proofs for the Determinant Identities, The Deduction Theorem for Strong Propositional Proof Systems, Proof Complexity of Non-classical Logics, Propositional proof complexity, Proof complexity of propositional default logic, The deduction theorem for strong propositional proof systems, Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II, Short proofs of the Kneser-Lovász coloring principle, Weak theories of linear algebra, The proof complexity of linear algebra, A bounded arithmetic AID for Frege systems, Quasipolynomial size proofs of the propositional pigeonhole principle, Polynomal-size Frege proofs of Bollobás' theorem on the trace of sets, Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds, Propositional Proofs in Frege and Extended Frege Systems (Abstract), Short Proofs of the Kneser-Lovász Coloring Principle, Logical Closure Properties of Propositional Proof Systems, On the correspondence between arithmetic theories and propositional proof systems – a survey
