A model of \(\widehat{R}^2_3\) inside a subexponential time resource

DOI10.1305/NDJFL/1039182248zbMath0967.03049OpenAlexW1567191326MaRDI QIDQ5937822

Eugenio Chinchilla

Publication date: 17 July 2001

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1039182248

zbMATH Keywords

bounded arithmeticcomputable functionsmodel of an induction schemeTuring machinewitnessing theorem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Nonstandard models of arithmetic (03H15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Models of arithmetic and set theory (03C62) Turing machines and related notions (03D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the scheme of induction for bounded arithmetic formulas
• Arithmetizing uniform \(NC\)
• Bounded arithmetic and the polynomial hierarchy
• Unprovability of consistency statements in fragments of bounded arithmetic
• Relating the bounded arithmetic and polynomial time hierarchies
• Notes on polynomially bounded arithmetic

This page was built for publication: A model of \(\widehat{R}^2_3\) inside a subexponential time resource