Remarks on recursion versus diagonalization and exponentially difficult problems

DOI10.1016/0022-0000(81)90042-8zbMath0468.68043OpenAlexW1973912119MaRDI QIDQ1156483

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)

Related Items (2)

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

Cites Work

• Indexings of subrecursive classes
• Minimal pairs of polynomial degrees with subexponential complexity
• Simple Gödel Numberings, Isomorphisms, and Programming Properties
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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