Teorema dell'accelerazione di Blum

Il teorema dell'accelerazione di Blum Nella teoria della complessità computazionale, Teorema dell'accelerazione di Blum, dichiarato per la prima volta da Manuel Blum in 1967, è un teorema fondamentale sulla complessità delle funzioni calcolabili.

Ogni funzione calcolabile ha un numero infinito di diverse rappresentazioni del programma in un dato linguaggio di programmazione. Nella teoria degli algoritmi si cerca spesso di trovare un programma con la più piccola complessità per una data funzione calcolabile e una data misura di complessità (un tale programma potrebbe essere definito ottimale). Il teorema dello speedup di Blum mostra che per qualsiasi misura di complessità esistono funzioni calcolabili che non sono ottimali rispetto a quella misura.[necessaria ulteriore spiegazione] Ciò esclude anche l'idea che esista un modo per assegnare a funzioni arbitrarie la loro complessità computazionale, intendendo l'assegnazione a qualsiasi f della complessità di un programma ottimo per f. Ciò ovviamente non esclude la possibilità di trovare la complessità di un programma ottimale per determinate funzioni specifiche.

Contenuti 1 Teorema di accelerazione 2 Guarda anche 3 Riferimenti 4 External links Speedup theorem Given a Blum complexity measure {stile di visualizzazione (varfi ,Phi )} e una funzione calcolabile totale {stile di visualizzazione f} con due parametri, allora esiste un predicato calcolabile totale {stile di visualizzazione g} (una funzione calcolabile con valore booleano) in modo che per ogni programma {stile di visualizzazione i} per {stile di visualizzazione g} , esiste un programma {stile di visualizzazione j} per {stile di visualizzazione g} in modo che per quasi tutti {stile di visualizzazione x} {stile di visualizzazione f(X,Phi _{j}(X))leq Phi _{io}(X),} {stile di visualizzazione f} è chiamata funzione di accelerazione. Il fatto che potrebbe essere in rapida crescita come desiderato (sempre che sia calcolabile) significa che il fenomeno di avere sempre un programma di minore complessità permane anche se da "più piccola" noi intendiamo "significativamente più piccolo" (per esempio, quadraticamente più piccolo, esponenzialmente più piccolo).

Vedi anche il teorema dell'accelerazione di Gödel Riferimenti Blum, Manuele (1967). "Una teoria indipendente dalla macchina della complessità delle funzioni ricorsive" (PDF). Giornale dell'ACM. 14 (2): 322–336. doi:10.1145/321386.321395. Da Emde Boas, Peter (1975). Becvar, Giorgio (ed.). "Dieci anni di accelerazione". Atti dei fondamenti matematici dell'informatica, 4esimo Simposio, Marianske Lazne, settembre 1-5, 1975. Appunti delle lezioni in Informatica. Springer-Verlag. 32: 13–29. doi:10.1007/3-540-07389-2_179.. Weissstein esterno sinistro, Eric W. "Teorema dell'accelerazione di Blum". Math World. Categorie: Teoremi nella teoria della complessità computazionale