Publication:4281694
From MaRDI portal
zbMath0795.03081MaRDI QIDQ4281694
Publication date: 7 April 1994
bounded arithmetic; fragments of arithmetic; finite Ramsey theorem; polynomial-size bounded-depth Frege proofs
Related Items
Expander Construction in VNC1, Approximate counting and NP search problems, Towards a Unified Complexity Theory of Total Functions, A lower bound on the size of resolution proofs of the Ramsey theorem, A note on propositional proof complexity of some Ramsey-type statements, Multifunction algebras and the provability of \(PH\downarrow\), Towards a unified complexity theory of total functions, A model-theoretic characterization of the weak pigeonhole principle, Expander construction in \(\mathrm{VNC}^1\), Upper and lower Ramsey bounds in bounded arithmetic, Separation results for the size of constant-depth propositional proofs