ON AVERAGE TIME HIERARCHIES

Authors
GOLDMANN M GRAPE P HASTAD J
Citation
M. Goldmann et al., ON AVERAGE TIME HIERARCHIES, Information processing letters, 49(1), 1994, pp. 15-20
Citations number
9
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
49
Issue
1
Year of publication
1994
Pages
15 - 20
Database
ISI
SICI code
0020-0190(1994)49:1<15:OATH>2.0.ZU;2-B
Abstract
For a time-constructible function T we give an explicit language L(T) which can be recognized in time T(n). We prove that any Turing machine that recognizes L(T) requires time close to T(n) for most inputs, thu s forming an average time hierarchy. The existence of the average time hierarchy was known, but depended on languages defined by complicated diagonalization. We also give simple proofs for the known stricter hi erarchy for functions.