On average time hierarchies
type: Item
instance of: scholarly article
title: On average time hierarchies
zbMATH Open document ID: 0787.68040
DOI: 10.1016/0020-0190(94)90048-5
author: Mikael Goldmann
author: Per Grape
author: Johan Hastad
published in: Information Processing Letters
publication date: 1994-02-24T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 500508
zbMATH Keywords: computational complexity
zbMATH Keywords: average time-complexity
zbMATH Keywords: hierarchy theorems
zbMATH Keywords: average time hierarchy
zbMATH Keywords: hierarchy for functions
MaRDI profile type: Publication
Wikidata QID: Q56959109
full work available at URL: 0020-0190(94)90048-5
OpenAlex ID: W2066875791
cites work: A Machine-Independent Theory of the Complexity of Recursive Functions
cites work: Average case completeness
cites work: On the Computational Complexity of Algorithms
cites work: Two-Tape Simulation of Multitape Turing Machines
cites work: Q4060387
cites work: Average Case Complete Problems
cites work: Q5593816
cites work: The foundations of mathematics. A study in the philosophy of science
DBLP publication ID: journals/ipl/GoldmannGH94
Recommended article: Q3343441
Recommended article: A generic time hierarchy with one bit of advice
Recommended article: Time hierarchies for sampling distributions
Recommended article: Time Hierarchies for Sampling Distributions
Recommended article: Q3476799
Recommended article: Tighter constant-factor time hierarchies
Recommended article: Q3488976
Recommended article: Delay and size in hierarchical organizations
Recommended article: Heuristic Time Hierarchies via Hierarchies for Sampling Distributions
description: scientific article; zbMATH DE number 500508