scientific article; zbMATH DE number 512985

MaRDI QIDQ4281694zbMATH OpenFDO

Authors Pavel Pudlák

Publication date 7 April 1994

zbMATH Keywords

bounded arithmeticfinite Ramsey theoremfragments of arithmeticpolynomial-size bounded-depth Frege proofs

Mathematics Subject Classification ID

Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Recommendations

• Upper and lower Ramsey bounds in bounded arithmetic
• A note on propositional proof complexity of some Ramsey-type statements
• On the strength of Ramsey's theorem
• Independence of Ramsey theorem variants using \(\varepsilon _0\)
• A rank lower bound for cutting planes proofs of Ramsey's theorem

Cited in

(19)

• Ramsey's theorem for sums, products, and arithmetic progressions
• Lifting independence results in bounded arithmetic
• Multifunction algebras and the provability of PH
• 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
• Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom
• scientific article; zbMATH DE number 6378629 (Why is no real title available?)
• A lower bound on the size of resolution proofs of the Ramsey theorem
• Expander construction in \(\mathsf{VNC}^1\)
• scientific article; zbMATH DE number 1453081 (Why is no real title available?)
• Towards a Unified Complexity Theory of Total Functions
• Approximate counting and NP search problems
• A packed Ramsey’s theorem and computability theory
• A note on propositional proof complexity of some Ramsey-type statements
• Ramsey theory on generalized Baire space
• Ramsey theory for countable binary homogeneous structures

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 Q4281694)