Fragments of bounded arithmetic and the lengths of proofs

DOI10.2178/jsl/1230396927zbMath1168.03044OpenAlexW2097024958MaRDI QIDQ5502825

Pavel Pudlák

Publication date: 9 January 2009

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1230396927

Mathematics Subject Classification ID

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

Related Items (5)

The provably total NP search problems of weak second order bounded arithmetic ⋮ Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic

Cites Work

• Unnamed Item
• Bounded arithmetic and the polynomial hierarchy
• On induction-free provability
• Herbrandizing search problems in Bounded Arithmetic
• Quantified propositional calculi and fragments of bounded arithmetic
• Bounds for proof-search and speed-up in the predicate calculus

This page was built for publication: Fragments of bounded arithmetic and the lengths of proofs