Blum's speedup theorem

Blum's speedup theorem 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 (such a program could be called optimal). Blum's speedup theorem shows that for any complexity measure there are computable functions that are not optimal with respect to that measure.[further explanation needed] This also rules out the idea there is a way to assign to arbitrary functions their computational complexity, meaning the assignment to any f of the complexity of an optimal program for f. This does of course not exclude the possibility of finding the complexity of an optimal program for certain specific functions.

Contents 1 Speedup theorem 2 See also 3 References 4 External links Speedup theorem Given a Blum complexity measure {displaystyle (varphi ,Phi )} and a total computable function {displaystyle f} with two parameters, then there exists a total computable predicate {displaystyle g} (a boolean valued computable function) so that for every program {displaystyle i} for {displaystyle g} , there exists a program {displaystyle j} for {displaystyle g} so that for almost all {displaystyle x} {displaystyle f(x,Phi _{j}(x))leq Phi _{i}(x),} {displaystyle f} is called the speedup function. The fact that it may be as fast-growing as desired (as long as it is computable) means that the phenomenon of always having a program of smaller complexity remains even if by "smaller" we mean "significantly smaller" (for instance, quadratically smaller, exponentially smaller).

See also Gödel's speed-up theorem References Blum, Manuel (1967). "A Machine-Independent Theory of the Complexity of Recursive Functions" (PDF). Journal of the ACM. 14 (2): 322–336. doi:10.1145/321386.321395. Van Emde Boas, Peter (1975). Bečvář, Jiří (ed.). "Ten years of speedup". Proceedings of Mathematical Foundations of Computer Science, 4th Symposium, Mariánské Lázně, September 1-5, 1975. Lecture Notes in Computer Science. Springer-Verlag. 32: 13–29. doi:10.1007/3-540-07389-2_179.. External links Weisstein, Eric W. "Blum's Speed-Up Theorem". MathWorld. Categories: Theorems in computational complexity theory

Si quieres conocer otros artículos parecidos a Blum's speedup theorem puedes visitar la categoría Theorems in computational complexity theory.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.


Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información