scientific article; zbMATH DE number 1420845

MaRDI QIDQ4944913zbMATH OpenFDO

Authors Jan Johannsen, Chris Pollett

Publication date 14 July 2002

zbMATH Keywords

bounded arithmeticcomplexity classcomprehension

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Publication:4893147
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Computer Science Logic
• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)
• Fragments of Bounded Arithmetic and Bounded Query Classes

Cited in

(8)

• Iterated multiplication in VTC^0
• Induction rules in bounded arithmetic
• Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
• Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\)
• A theory for Log-Space and NLIN versus co-NLIN
• Construction of models of bounded arithmetic by restricted reduced powers
• On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)
• Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\)

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