Blum's speedup theorem

Today it means: A fundamental theorem about the complexity of computable functions, stating that for any complexity measure there are computable functions that are not optimal with respect to that measure. Full definition →