scientific article; zbMATH DE number 440478
From MaRDI portal
Publication:3140635
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
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)