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

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).

Authors

• John G. Geske
• Dung T. Huynh
• Joel I. Seiferas

Keywords

No keywords are indexed for this paper.