End extensions of models of linearly bounded arithmetic

DOI10.1016/S0168-0072(97)00026-2MaRDI QIDQ1377910zbMATH OpenFDO

Authors Domenico Zambella

Publication date 28 June 1998

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

bounded arithmeticpolynomial hierarchyend extensionsmodels of arithmetic

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Second- and higher-order arithmetic and fragments (03F35) Models of arithmetic and set theory (03C62)

Recommendations

• End-extensions of models of weak arithmetic from complexity-theoretic containments
• End-extending models of $IΔ_0 + exp + ΒΣ_1$
• Notes on polynomially bounded arithmetic

Cites work

• scientific article; zbMATH DE number 440487 (Why is no real title available?)
• scientific article; zbMATH DE number 4137758 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• Combinatorial principles in elementary number theory
• Counting $Δ_0$ sets
• Notes on polynomially bounded arithmetic
• On the scheme of induction for bounded arithmetic formulas
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Relating the bounded arithmetic and polynomial time hierarchies

Cited in

(5)

• A theory for Log-Space and NLIN versus co-NLIN
• Iterated multiplication in \(VTC^0\)
• End-extensions of models of weak arithmetic from complexity-theoretic containments
• Truth definitions without exponentiation and the \(\Sigma _{1}\) collection scheme
• Separations of first and second order theories in bounded arithmetic

This page was built for publication: End extensions of models of linearly bounded arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377910)