Fragments of bounded arithmetic and the lengths of proofs
From MaRDI portal
Recommendations
- Quantified propositional calculi and fragments of bounded arithmetic
- Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
- scientific article; zbMATH DE number 1070621
- Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic
- Bounded arithmetic and truth definition
Cites work
- Bounded arithmetic and the polynomial hierarchy
- Bounds for proof-search and speed-up in the predicate calculus
- Herbrandizing search problems in Bounded Arithmetic
- scientific article; zbMATH DE number 1195552 (Why is no real title available?)
- On induction-free provability
- Quantified propositional calculi and fragments of bounded arithmetic
Cited in
(18)- Lifting independence results in bounded arithmetic
- Bounded arithmetic, proof complexity and two papers of Parikh
- What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?
- Quantified propositional calculi and fragments of bounded arithmetic
- scientific article; zbMATH DE number 4145897 (Why is no real title available?)
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- Approximation and Small-Depth Frege Proofs
- Polynomially and superexponentially shorter proofs in fragments of arithmetic
- scientific article; zbMATH DE number 7162237 (Why is no real title available?)
- Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
- scientific article; zbMATH DE number 2196511 (Why is no real title available?)
- scientific article; zbMATH DE number 5053656 (Why is no real title available?)
- scientific article; zbMATH DE number 963569 (Why is no real title available?)
- 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
- Alternating minima and maxima, Nash equilibria and bounded arithmetic
- Tractable fragments of Presburger arithmetic
- Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic
This page was built for publication: Fragments of bounded arithmetic and the lengths of proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502825)
