Name
Abstract | ||
|---|---|---|
For certain computational models, a constant-factor time hierarchy theorem is known, showing that a constant-factor difference in time bounds makes a difference in problem-solving power (unlike the situation with Turing machines). In this paper we apply the classic "translational technique" (padding) to these hierarchies and show that they are tighter than indicated by the previous proofs. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0020-0190(03)00253-9 | Inf. Process. Lett. |
Keywords | Field | DocType |
turing machine,constant-factor time hierarchy theorem,time bound,tighter constant-factor time hierarchy,translational technique,certain computational model,constant-factor difference,previous proof,problem-solving power,computational complexity,computer model | Discrete mathematics,Combinatorics,Mathematical proof,Turing machine,Time complexity,Hierarchy,Time hierarchy theorem,Padding,Padding argument,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
87 | 1 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amir M Ben-Amram | 1 | 327 | 30.52 |