Blum's speedup theorem

From Wiktionary, the free dictionary
Archived revision by Equinox (talk | contribs) as of 01:08, 2 June 2019.
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

English

English Wikipedia has an article on:
Wikipedia

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.
Retrieved from "https://en.wiktionary.org/w/index.php?title=Blum%27s_speedup_theorem&oldid=53217930"