There exists a total computable predicate such that for any algorithm computing with running time , there exists another algorithm computing with computation time.
This means that there is no algorithm for the predicate that is even nearly optimal.
Blum, M. "A Machine-Independent Theory of the Complexity of Recursive Functions." J. ACM14, 322-336, 1967.Seiferas,
J. I. and Meyer, A. R. "Characterization of Realizable Space Complexities."
Ann. Pure Appl. Logic73, 171-190, 1995.
such that for any algorithm computing 
with running time 
, there exists another algorithm computing 
with computation time 
.
that is even nearly optimal.
