Strong time bounds: Non-computable bounds and a hierarchy theorem
type: Item
instance of: scholarly article
title: Strong time bounds: Non-computable bounds and a hierarchy theorem
zbMATH Open document ID: 0694.68038
DOI: 10.1016/0304-3975(90)90181-G
published in: Theoretical Computer Science
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4137328
zbMATH Keywords: time bounds
zbMATH Keywords: hierarchy
zbMATH Keywords: complexity of computation
zbMATH Keywords: computable functions
author: John Michael Robson
MaRDI profile type: Publication
cites work: Q3033315
cites work: Time bounded random access machines
cites work: On genuinely time bounded computations
Recommended article: On genuinely time bounded computations
Recommended article: Almost-everywhere complexity hierarchies for nondeterministic time
Recommended article: Strong computational lower bounds via parameterized complexity
Recommended article: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
Recommended article: On lower bounds for the time of computation
Recommended article: A second step toward the strong polynomial-time hierarchy
Recommended article: Q3355230
Recommended article: Deterministic versus nondeterministic time and lower bound problems
Recommended article: Nontriviality for Exponential Time w.r.t. Weak Reducibilities
description: scientific article; zbMATH DE number 4137328