Blums speedup-sats

I beräkningskomplexitetsteorin är Blums speedup-teorem , som först utgavs av Manuel Blum 1967, en grundläggande teorem om komplexiteten hos beräkningsbara funktioner .

Varje beräkningsbar funktion har ett oändligt antal olika programrepresentationer i ett givet programmeringsspråk. I teorin om algoritmer strävar man ofta efter att hitta ett program med den minsta komplexiteten för en given beräkningsbar funktion och ett givet komplexitetsmått (ett sådant program skulle kunna kallas optimalt ). Blums speedup-sats visar att det för varje komplexitetsmått finns en beräkningsbar funktion, så att det inte finns något optimalt program som beräknar den, eftersom varje program har ett program med lägre komplexitet. Detta utesluter också idén att det finns ett sätt att tilldela godtyckliga funktioner deras beräkningskomplexitet, vilket betyder tilldelningen till någon f av komplexiteten hos ett optimalt program för f . Detta utesluter naturligtvis inte möjligheten att hitta komplexiteten i ett optimalt program för vissa specifika funktioner.

Speedup-sats

Givet ett Blum-komplexitetsmått $(\varphi ,\Phi )$ och en total beräkningsbar funktion $f$ med två parametrar, så finns det ett totalt beräkningsbart predikat $g$ ( en booleskt värderad beräkningsbar funktion) så att det för varje program $i$ för $g$ finns ett program $j$ för $g$ så att för nästan alla ${\ displaystil x}$

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

$f$ kallas snabbhetsfunktionen . Det faktum att det kan växa så snabbt som önskat (så länge det är beräkningsbart) betyder att fenomenet att alltid ha ett program med mindre komplexitet kvarstår även om vi med "mindre" menar "betydligt mindre" (till exempel kvadratiskt mindre, exponentiellt mindre).

Se även

• Gödels hastighetssats

• Blum, Manuel (1967). "En maskinoberoende teori om komplexiteten hos rekursiva funktioner" ( PDF) . Journal of the ACM . 14 (2): 322–336. doi : 10.1145/321386.321395 .
• Van Emde Boas, Peter (1975). Bečvář, Jiří (red.). "Tio år av speedup". Proceedings of Mathematical Foundations of Computer Science, 4th Symposium, Mariánské Lázně, 1-5 september 1975 . Föreläsningsanteckningar i datavetenskap. Springer-Verlag. 32 : 13–29. doi : 10.1007/3-540-07389-2_179 . .

externa länkar

• Weisstein, Eric W. "Blums hastighetssats" . MathWorld .