Remarks on recursion versus diagonalization and exponentially difficult problems

DOI10.1016/0022-0000(81)90042-8zbMath0468.68043MaRDI 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 bounds; Presburger arithmetic; limited halting problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

68W99: Algorithms in computer science

Related Items

Diagonalization, uniformity, and fixed-point theorems