Blum's speedup theorem
id:
blum-s-speedup-theorem-252-14346464
title:
Blum's speedup theorem
text:
In computational complexity theory, Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions. Each computable function has an infinite number of different program representations in a given programming language. In the theory of algorithms one often strives to find a program with the smallest complexity for a given computable function and a given complexity measure. Blum's speedup theorem shows that for any complexity meas
brand slug:
wiki
category slug:
encyclopedia
description:
Rules out assigning to arbitrary functions their computational complexity
original url:
https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem
date created:
date modified:
2023-12-30T20:05:13Z
main entity:
{"identifier":"Q1751105","url":"https://www.wikidata.org/entity/Q1751105"}
image:
fields total:
13
integrity:
14