Théorème d'accélération de Blum

Théorème d'accélération de Blum dans la théorie de la complexité computationnelle, Théorème d'accélération de Blum, déclaré pour la première fois par Manuel Blum dans 1967, est un théorème fondamental sur la complexité des fonctions calculables.

Chaque fonction calculable a un nombre infini de représentations de programme différentes dans un langage de programmation donné. Dans la théorie des algorithmes, on s'efforce souvent de trouver un programme avec la plus petite complexité pour une fonction calculable donnée et une mesure de complexité donnée (un tel programme pourrait être qualifié d'optimal). Le théorème d'accélération de Blum montre que pour toute mesure de complexité, il existe des fonctions calculables qui ne sont pas optimales par rapport à cette mesure.[plus d'explications nécessaires] Cela exclut également l'idée qu'il existe un moyen d'attribuer à des fonctions arbitraires leur complexité de calcul, c'est-à-dire l'affectation à tout f de la complexité d'un programme optimal pour f. Cela n'exclut bien sûr pas la possibilité de trouver la complexité d'un programme optimal pour certaines fonctions spécifiques.

Contenu 1 Théorème d'accélération 2 Voir également 3 Références 4 External links Speedup theorem Given a Blum complexity measure {style d'affichage (varphi ,Phi )} et une fonction calculable totale {style d'affichage f} avec deux paramètres, alors il existe un prédicat calculable total {style d'affichage g} (une fonction calculable à valeur booléenne) de sorte que pour chaque programme {style d'affichage i} pour {style d'affichage g} , il existe un programme {displaystyle j} pour {style d'affichage g} de sorte que pour presque tous {style d'affichage x} {style d'affichage f(X,Phi _{j}(X))leq Phi _{je}(X),} {style d'affichage f} s'appelle la fonction d'accélération. Le fait qu'il puisse être à croissance aussi rapide que souhaité (tant qu'il est calculable) signifie que le phénomène d'avoir toujours un programme de plus petite complexité demeure même si par "plus petit" nous voulons dire "nettement plus petit" (par exemple, quadratiquement plus petit, exponentiellement plus petit).

Voir aussi le théorème d'accélération de Gödel Références Blum, Manuel (1967). "Une théorie indépendante de la machine de la complexité des fonctions récursives" (PDF). Journal de l'ACM. 14 (2): 322–336. est ce que je:10.1145/321386.321395. Depuis Emde Boas, Pierre (1975). Becvar, George (éd.). "Dix ans d'accélération". Actes des Fondements Mathématiques de l'Informatique, 4ème Symposium, Marianske Lazne, Septembre 1-5, 1975. Notes de cours en informatique. Springer Verlag. 32: 13–29. est ce que je:10.1007/3-540-07389-2_179.. Weissstein externe gauche, Eric W. "Théorème d'accélération de Blum". MathWorld. Catégories: Théorèmes de la théorie de la complexité computationnelle