A note on almost-everywhere-complex sets and separating deterministic-time-complexity classes

AbstractFor each time bound T: {input strings} → {natural numbers} that is some machine's exact running time, there is a {0, 1}-valued function fT that can be computed within time proportional to T, but that cannot be computed within any time bound T′ that is infinitely often significantly smaller than T (T′ ≠ Ω(T), typically). Equivalently, every algorithm to compute fT requires time T′ on almost every input if T′ is almost everywhere significantly smaller than T (T′ = o(T), typically)