End extensions of models of linearly bounded arithmetic

DOI10.1016/S0168-0072(97)00026-2zbMath0891.03032MaRDI QIDQ1377910

Domenico Zambella

Publication date: 28 June 1998

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

zbMATH Keywords

bounded arithmeticpolynomial hierarchymodels of arithmeticend extensions

Mathematics Subject Classification ID

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

Related Items (5)

Truth definitions without exponentiation and the Σ₁ collection scheme ⋮ Separations of first and second order theories in bounded arithmetic ⋮ Iterated multiplication in \(VTC^0\) ⋮ END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS ⋮ A theory for Log-Space and NLIN versus co-NLIN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the scheme of induction for bounded arithmetic formulas
• Combinatorial principles in elementary number theory
• Relating the bounded arithmetic and polynomial time hierarchies
• Counting $Δ_0$ sets
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Notes on polynomially bounded arithmetic

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