Twierdzenie Bluma o przyspieszeniu
W teorii złożoności obliczeniowej twierdzenie Bluma o przyspieszeniu , po raz pierwszy sformułowane przez Manuela Bluma w 1967 r., jest podstawowym twierdzeniem o złożoności funkcji obliczalnych .
Każda funkcja obliczalna ma nieskończoną liczbę różnych reprezentacji programu w danym języku programowania. W teorii algorytmów często dąży się do znalezienia programu o najmniejszej złożoności dla danej funkcji obliczalnej i danej miary złożoności (program taki można by nazwać optymalnym ). Twierdzenie Bluma o przyspieszeniu pokazuje, że dla dowolnej miary złożoności istnieje funkcja obliczalna, tak że nie ma optymalnego programu, który ją oblicza, ponieważ każdy program ma program o mniejszej złożoności. To również wyklucza pomysł, że istnieje sposób przypisania dowolnym funkcjom ich złożoności obliczeniowej, co oznacza przypisanie dowolnej f złożoności optymalnego programu dla f . Nie wyklucza to oczywiście możliwości znalezienia złożoności optymalnego programu dla określonych funkcji.
Twierdzenie o przyspieszeniu
Biorąc pod uwagę i obliczalną funkcję parametrami , istnieje całkowity predykat ja dla sol istnieje program sol , że dla prawie wszystkich
nazywa się funkcją przyspieszenia . Fakt, że może rosnąć tak szybko, jak jest to pożądane (o ile jest obliczalny), oznacza, że zjawisko posiadania zawsze programu o mniejszej złożoności pozostaje, nawet jeśli przez „mniejszy” rozumiemy „znacznie mniejszy” (na przykład kwadratowy mniejszy, wykładniczo mniejszy).
Zobacz też
- Blum, Manuel (1967). „Niezależna od maszyny teoria złożoności funkcji rekurencyjnych” (PDF) . Dziennik ACM . 14 (2): 322–336. doi : 10.1145/321386.321395 .
- Van Emde Boas, Peter (1975). Bečvář, Jiří (red.). „Dziesięć lat przyspieszenia” . Proceedings of Mathematical Foundations of Computer Science, IV Sympozjum, Mariánské Lázně, 1-5 września 1975 . Notatki z wykładów z informatyki. Springer-Verlag. 32 : 13–29. doi : 10.1007/3-540-07389-2_179 . .