블럼 스피드 업 정리

계산 복잡성 이론에서 1967년 마누엘 블럼이 처음 밝힌 블럼의 스피드 업 정리는 계산 가능한 기능의 복잡성에 대한 근본적인 정리다.

계산 가능한 각 함수는 주어진 프로그래밍 언어로 무한히 많은 다른 프로그램 표현을 가지고 있다.알고리즘 이론에서 사람들은 종종 주어진 계산 가능한 기능과 주어진 복잡성 측정에 대해 가장 작은 복잡성을 가진 프로그램을 찾으려고 노력한다(그런 프로그램을 최적 프로그램이라고 부를 수 있다).블럼의 속도 상승 정리는 어떤 복잡성 측정에 대해서도 그 측도에 대해 최적적이지 않은 계산 가능한 함수가 있다는 것을 보여준다.^{[further explanation needed]}이것은 또한 임의 함수의 계산 복잡성에 할당하는 방법이 있다는 생각을 배제한다. 즉, f에 대한 최적 프로그램의 복잡성에 대한 할당을 의미한다.이것은 물론 특정 기능에 대한 최적 프로그램의 복잡성을 발견할 가능성을 배제하지 않는다.

스피드업 정리

블럼 복잡도 측정$({\displaystyle \phi }$ ,${\displaystyle \mathrm{\phi }}$) ${\displaystyle (\varphi ,\Phi )}$과 두 개의 매개 변수를 가진$$ 총 계산 가능한 $함수{\displaystyle }$ f ${\displaystyle f}$이(가) 주어지면, 모든 $프로그램{\displaystyle }$ i$$${\disp$에 대해 계산 $가능$한 총 계산 가능한 술어 g {\$displaystyle$ $i$$}$이 $있다$.$$$laystyle{\displaystyle }$ $g$$},$ g {\$displaystyle g}$에 $대한{\displaystyle }$프로그램 j {\$displaystyle$ j$}$이$($가) 존재하여$$ 거의 모든$x{\displaystyle }$ {\$displaystyle x}$에 대해 사용됨

${\displaystyle f(x,\Phi _{j}(x)\leq \Phi _{i}(x)\,}$

$[\displaystyle f}$는 스피드업 함수라고 불린다$$.그것이 원하는 만큼 빠르게 성장할 수 있다는 사실은 (계산 가능한 한) 우리가 "더 작다"고 해도, 항상 더 작은 복잡성의 프로그램을 갖는 현상이 남아 있다는 것을 의미한다(예를 들어, 2차적으로 더 작다, 기하급수적으로 더 작다.

참고 항목

• 괴델의 스피드 업 정리

참조

• 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..

외부 링크

• Weisstein, Eric W. "Blum's Speed-Up Theorem". MathWorld.