Remarks on recursion versus diagonalization and exponentially difficult problems

DOI10.1016/0022-0000(81)90042-8MaRDI QIDQ1156483zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1981

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(81)90042-8

zbMATH Keywords

lower boundsPresburger arithmeticlimited halting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Algorithms in computer science (68W99)

Cites work

• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3566170 (Why is no real title available?)
• scientific article; zbMATH DE number 3586480 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3073037 (Why is no real title available?)
• Indexings of subrecursive classes
• Minimal pairs of polynomial degrees with subexponential complexity
• Simple Gödel Numberings, Isomorphisms, and Programming Properties

Cited in

(2)

• Composition is almost (but not quite) as good as \(s-1-1\)
• Diagonalization, uniformity, and fixed-point theorems

This page was built for publication: Remarks on recursion versus diagonalization and exponentially difficult problems

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