What is it about?
One is usually tempted to believe that any computable function has an "intrinsic" computational complexity. Blum's speedup Theorem proves that this is not the case: there are functions such that the complexity of ANY algorithm computing it can be improved by an arbitrary speedup. This was proved by Blum in the context of general recursive functions. We repeat the proof in the more constrained primitive recursive setting.
Featured Image
Photo by JC Dela Cuesta on Unsplash
Why is it important?
The proof was part of a program aimed to better understand the key properties used in major theorems of computational complexity, striving for a more abstract, axiomatic approach to complexity theory.
Read the Original
This page is a summary of: The Speedup Theorem in a Primitive Recursive Framework, January 2015, ACM (Association for Computing Machinery),
DOI: 10.1145/2676724.2693178.
You can read the full text:
Contributors
The following have contributed to this page
