A model theoretic proof of a subexponential time witnessing theorem

DOI10.1016/S0764-4442(98)80113-4MaRDI QIDQ4217552zbMATH OpenWikidataFDO

Authors Eugenio Chinchilla

Publication date 11 November 1998

Published in Comptes Rendus de l'Académie des Sciences - Series I - Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0764-4442(98)80113-4

zbMATH Keywords

model of an induction schemeTuring machinewitnessing theorem

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Nonstandard models of arithmetic (03H15)

Recommendations

• A model of \(\widehat{R}^2_3\) inside a subexponential time resource
• scientific article; zbMATH DE number 67686
• scientific article; zbMATH DE number 4006252

Cited in

(4)

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• A model of \(\widehat{R}^2_3\) inside a subexponential time resource
• Bootstrapping. I
• A purely model-theoretic proof of the exponential succinctness gap between CTL\(^{+}\) and CTL

This page was built for publication: A model theoretic proof of a subexponential time witnessing theorem

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