Remarks on recursion versus diagonalization and exponentially difficult problems
type: Item
instance of: scholarly article
title: Remarks on recursion versus diagonalization and exponentially difficult problems
zbMATH Open document ID: 0468.68043
DOI: 10.1016/0022-0000(81)90042-8
author: S. H. Smith
published in: Journal of Computer and System Sciences
publication date: 1981-01-01T00:00:00Z
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 3735132
zbMATH Keywords: lower bounds
zbMATH Keywords: limited halting problems
zbMATH Keywords: Presburger arithmetic
MaRDI profile type: Publication
full work available at URL: 0022-0000(81)90042-8
OpenAlex ID: W1973912119
cites work: Q4138136
cites work: Q4082296
cites work: Q5812175
cites work: Indexings of subrecursive classes
cites work: Minimal pairs of polynomial degrees with subexponential complexity
cites work: Simple Gödel Numberings, Isomorphisms, and Programming Properties
cites work: Q4153600
cites work: Q5573961
description: scientific article; zbMATH DE number 3735132