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.
This article is issued from Wiktionary. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.