Blum's speedup theorem
Jump to navigation
Jump to search
English
[edit]Etymology
[edit]First stated by Manuel Blum in 1967.
Proper noun
[edit]- (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.