English Explanatory Dictionary

Blum's speedup theorem

English dictionary entry

Meanings

name
  1. 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.

Word forms

Blum's speedup theorem

Etymology

First stated by Manuel Blum in 1967.

This entry uses open data from Wiktionary (CC BY-SA/GFDL). Word forms are used for search and are not indexed as separate pages.
Back to search All on B Russian dictionary Dahl dictionary