Teorema accelerării lui Blum

În teoria complexității de calcul , teorema accelerării lui Blum , propusă de Manuel Blum în 1967, este o teoremă importantă a accelerării privind complexitatea funcțiilor calculabile .

Fiecare funcție calculabilă are un număr infinit de reprezentări diferite într-un limbaj de programare dat. În teoria calculabilității există adesea necesitatea de a găsi un algoritm de complexitate mai mică pentru o funcție calculabilă dată și o clasă de complexitate dată.

Teorema de accelerare a lui Blum susține că pentru fiecare clasă de complexitate există funcții calculabile pentru a căror procesare nu există programe mai eficiente (mai rapide).

Definiție

Având o funcție totală ( recursivă ) $r(x,y)$ ${\ displaystyle r (x, y)}$ ${\ displaystyle r (x, y)}$ (cu doi parametri), atunci există o funcție totală $f$ ${\ displaystyle f}$ $f$ (boolean, adică cu $Codf=\{0,1\}$ ${\ displaystyle Codf = \ {0,1 \}}$ ${\ displaystyle Codf = \ {0,1 \}}$ ) (sau predicat recursiv echivalent) astfel încât pentru fiecare program (algoritm) $the$ ${\ displaystyle i}$ $the$ pentru $f$ ${\ displaystyle f}$ $f$ , există un program $j$ ${\ displaystyle j}$ $j$ pentru $f$ ${\ displaystyle f}$ $f$ , astfel încât pentru aproape toți $X$ ${\ displaystyle x}$ $X$ apare că $r(x,\Phi _{j}(x))\leq \Phi _{i}(x)$ ${\ displaystyle r (x, \ Phi _ {j} (x)) \ leq \ Phi _ {i} (x)}$ ${\ displaystyle r (x, \ Phi _ {j} (x)) \ leq \ Phi _ {i} (x)}$

Functia $r$ ${\ displaystyle r}$ $r$ se numește funcția de accelerare .

Simplificând, există mai mulți algoritmi pentru care nu există un algoritm mai rapid, ca pentru fiecare mașină Turing care implementează programul $the$ ${\ displaystyle i}$ $the$ , există întotdeauna unul (care implementează $j$ ${\ displaystyle j}$ $j$ ) mai performant.

Bibliografie

Manuel Blum , O teorie independentă de mașini a complexității funcțiilor recursive , în Jurnalul ACM , vol. 14, 1967, pp. 322–336, DOI : 10.1145 / 321386.321395 .
Peter van Emde Boas, Zece ani de accelerare, Proceedings of MFCS (Jirí Becvár, ed.), Lecture Notes in Computer Science, vol. 32, Springer, 1975, pp. 13-29.

linkuri externe

(EN) Eric W. Weisstein, Teorema accelerării Blum , în MathWorld Wolfram Research.

Portal IT

Portalul de matematică