I&C Journal 1991 Journal Article
A note on almost-everywhere-complex sets and separating deterministic-time-complexity classes
- John G. Geske
- Dung T. Huynh
- Joel I. Seiferas
For each time bound T: {input strings} → {natural numbers} that is some machine's exact running time, there is a {0, 1}-valued function f T 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 f T requires time T′ on almost every input if T′ is almost everywhere significantly smaller than T (T′ = o(T), typically).