Blum's speedup theorem

English

Etymology

First stated by Manuel Blum in 1967.

Proper noun

Blum's speedup theorem

1. (computing theory) 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.