linguistic:voice_change
Sharper hierarchy theorems

The gap of approximately log f (n) {\displaystyle \log f(n)} between the lower and upper time bound in the hierarchy theorem can be traced to the efficiency of the device used in the proof, namely a universal program that maintains a step-count. This can be done more efficiently on certain computational models. The sharpest results, presented below, have been proved for:

For these models, the theorem has the following form:

If f (n) is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic time f (n) but can be solved in worst-case time af (n) for some constant a (dependent on f).

Thus, a constant-factor increase in the time bound allows for solving more problems, in contrast with the situation for Turing machines (see Linear speedup theorem). Moreover, Ben-Amram proved that, in the above models, for f of polynomial growth rate (but more than linear), it is the case that for all ε > 0 {\displaystyle \varepsilon >0}, there exists a decision problem which cannot be solved in worst-case deterministic time f (n) but can be solved in worst-case time (1 + ε) f (n) {\displaystyle (1+\varepsilon)f(n)}.