Beschleunigungssatz von Blum

Blums Beschleunigungstheorem in der Theorie der rechnerischen Komplexität, Beschleunigungssatz von Blum, erstmals erwähnt von Manuel Blum in 1967, ist ein grundlegender Satz über die Komplexität berechenbarer Funktionen.

Jede berechenbare Funktion hat eine unendliche Anzahl verschiedener Programmdarstellungen in einer gegebenen Programmiersprache. In der Theorie der Algorithmen ist man oft bestrebt, für eine gegebene berechenbare Funktion und ein gegebenes Komplexitätsmaß ein Programm mit der kleinsten Komplexität zu finden (ein solches Programm könnte als optimal bezeichnet werden). Der Beschleunigungssatz von Blum zeigt, dass es für jedes Komplexitätsmaß berechenbare Funktionen gibt, die in Bezug auf dieses Maß nicht optimal sind.[weitere Erklärung nötig] Dies schließt auch die Idee aus, dass es eine Möglichkeit gibt, beliebigen Funktionen ihre Rechenkomplexität zuzuweisen, also die Zuordnung der Komplexität eines optimalen Programms für f zu jedem f. Dies schließt natürlich die Möglichkeit nicht aus, die Komplexität eines optimalen Programms für bestimmte spezifische Funktionen zu finden.

Inhalt 1 Speedup-Theorem 2 Siehe auch 3 Verweise 4 External links Speedup theorem Given a Blum complexity measure {Anzeigestil (Varphi ,Phi )} und eine vollständig berechenbare Funktion {Anzeigestil f} mit zwei Parametern, dann gibt es ein total berechenbares Prädikat {Anzeigestil g} (eine boolesche berechenbare Funktion) also für jedes programm {Anzeigestil i} zum {Anzeigestil g} , Es gibt ein Programm {Anzeigestil j} zum {Anzeigestil g} also für fast alle {Anzeigestil x} {Anzeigestil f(x,Phi_{j}(x))leq Phi _{ich}(x),} {Anzeigestil f} wird Beschleunigungsfunktion genannt. Die Tatsache, dass es so schnell wachsen darf wie gewünscht (solange es berechenbar ist) bedeutet, dass das Phänomen, immer ein Programm mit geringerer Komplexität zu haben, auch wenn durch bleibt "kleiner" wir meinen "deutlich kleiner" (zum Beispiel, quadratisch kleiner, exponentiell kleiner).

Siehe auch Beschleunigungssatz von Gödel Literatur Blum, Manuel (1967). "Eine maschinenunabhängige Theorie der Komplexität rekursiver Funktionen" (Pdf). Zeitschrift der ACM. 14 (2): 322–336. doi:10.1145/321386.321395. Von Emde Boas, Peter (1975). Becvar, George (ed.). "Zehn Jahre Beschleunigung". Proceedings of Mathematical Foundations of Computer Science, 4th Symposium, Marienbad, September 1-5, 1975. Vorlesungsunterlagen in Informatik. Springer-Verlag. 32: 13–29. doi:10.1007/3-540-07389-2_179.. External links Weisstein, Erich W. "Beschleunigungssatz von Blum". MathWorld. Kategorien: Theoreme der Computational Complexity Theoreme