scientific article; zbMATH DE number 440478

zbMATH Open0793.03046MaRDI QIDQ3140635FDOQ3140635

Authors: Peter Clote 

Publication date: 21 August 1994

Title of this publication is not available (Why is that?)

Recommendations

• Polynomial size proofs of the propositional pigeonhole principle
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Propositional proofs in Frege and extended Frege systems (abstract)
• Quasipolynomial size proofs of the propositional pigeonhole principle
• Exponential lower bounds for the pigeonhole principle

zbMATH Keywords

combinatorial principlesFrege proofALOGTIME computable functionspolynomial-size proofs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (9)

• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)
• The equivalence of theories that characterize ALogTime
• Function-algebraic characterizations of log and polylog parallel time
• Computation models and function algebras
• On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
• On a Theory for AC0 and the Strength of the Induction Scheme
• A bounded arithmetic AID for Frege systems
• Tractability of cut-free Gentzen type propositional calculus with permutation inference

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140635)