Remarks on recursion versus diagonalization and exponentially difficult problems

DOI10.1016/0022-0000(81)90042-8zbMATH Open0468.68043OpenAlexW1973912119MaRDI QIDQ1156483FDOQ1156483

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Simple Gödel Numberings, Isomorphisms, and Programming Properties
• Indexings of subrecursive classes
• Minimal pairs of polynomial degrees with subexponential complexity
• Title not available (Why is that?)

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)