Tighter constant-factor time hierarchies
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. (C) 2003 Published by Elsevier Science B.V.
hierarchy theorem computational complexity padding argument