Pourquoi le temps polynomial est appelé "efficace"?

Pourquoi en informatique, toute complexité au plus polynomiale est considérée comme efficace?

Pour toute application pratique ^(a) , les algorithmes de complexité sont bien plus rapides que les algorithmes qui s'exécutent dans le temps, par exemple n 80 , mais le premier est considéré comme inefficace alors que le second est efficace. Où est la logique?!$n^{\log n}$$n^{80}$

^{(a) Supposons, par exemple, que le nombre d'atomes dans l'univers est d'environ .$10^{80}$}

Un autre point de vue sur "l'efficacité" est que le temps polynomial nous permet de définir une notion "d'efficacité" qui ne dépend pas des modèles de machine. Plus précisément, il existe une variante de la thèse de Church-Turing appelée "thèse efficace de Church-Turing", selon laquelle tout problème qui s'exécute en temps polynomial sur un type de modèle de machine s'exécutera également en temps polynomial sur un autre modèle de machine tout aussi puissant.

Ceci est une affirmation plus faible de la thèse générale de la tomodensitométrie, et est "en quelque sorte" violée à la fois par des algorithmes aléatoires et des algorithmes quantiques, mais n'a pas été violée dans le sens où elle est capable de résoudre un problème NP-difficile en temps réel en modifiant le modèle de la machine.

C'est finalement la raison pour laquelle le temps polynomial est une notion populaire en théorieCS. Cependant, la plupart des gens se rendent compte que cela ne reflète pas "l'efficacité pratique". Pour plus d'informations à ce sujet, l'article de Dick Lipton sur les « algorithmes galactiques » est une excellente lecture.

$O(n^{80})$$O(n^{\log n})$$n > 1208925819614629174706176$

$n^{\log n}$$n^{80}$

Par exemple, la plupart des bibliothèques pour la multiplication d’entiers, par exemple GMP implémentera une combinaison d’algorithmes et sélectionneront un algorithme inférieur en fonction de la taille d’entrée, sélectionneront les algorithmes pratiquement supérieurs en fonction de la taille d’entrée, bien que ces algorithmes puissent être asymptotiquement inférieurs. Certains algorithmes asymptotiquement "inférieurs" seront plus rapides sur certaines tailles d’entrée et seront sélectionnés par rapport aux algorithmes optimaux.

$O(n^{2.3737})$

La théorie TL; DR se préoccupe du comportement asymptotique afin de comparer les algorithmes car la taille limite d'entrée est arbitrairement grande.

Cette réponse examinera le contexte "plus grand image" de votre question. La science informatique est en fait une science relativement jeune et quelque peu ouverte et elle n’a pas encore de bonnes réponses ni même de bonnes réponses à certaines questions fondamentales. La question fondamentale "qu'est-ce qui est efficacement calculé" est soit formulée de manière précise ou grossière dans CS (selon l'opinion) sous le nom du fameux problème P vs NP (ou le problème étroitement lié P / Exptime), et est toujours ouverte après plus de quatre décennies de initiée par Cook / Levin ~ 1970 et par le travail intense des plus grands informaticiens du monde (et de nombreux mathématiciens s'intéressent également au problème, qui est fondamental).

En d'autres termes, même avec une définition approximative du terme "efficient" comme "temps P" et une des récompenses scientifiques les plus estimées - à savoir un prix d'un million de dollars attaché au problème depuis plus de 10 ans - l'informatique ne peut même pas prouver que certains problèmes (proches de cette limite) doit ou ne doit pas avoir d’algorithmes efficaces (Ptime). Par conséquent, la définition exacte du terme "efficace", plus précise que le temps P, n’est ni nécessaire ni même possible à ce stade. Si / quand la conjecture P vs NP est établie d'une manière ou d'une autre, une définition plus stricte du terme "efficace" peut ou devrait être possible.

En outre, on pourrait penser que la définition de "efficace" donnée par Ptime pourrait même être un peu "bâclée", et la plupart des informaticiens seraient probablement d'accord avec cela, et la plupart d'entre eux pensent que la conjecture P vs NP est de la plus haute importance pour résoudre, le point qu'ils pourraient même considérer cette affirmation ou cette observation comme triviale ... autrement dit, pour ainsi dire, c'est un travail en cours / nous y travaillons . (En fait, les informaticiens grand public vont même si loin, en plaisantant à moitié, pour qualifier d' embarras le fossé et le manque de progrès / les séparations définitives .)

En fait, il existe même une conjecture étroitement liée / significativement plus forte que P vs NP, à savoir NP vs P / poly, qui ne peut pas non plus être résolue par la science informatique pour le moment. il suppose que les problèmes de temps NP ne peuvent être résolus par aucun circuit de "taille P", c'est-à-dire qu'il n'est même pas limité aux circuits pouvant être créés par des algorithmes / machines de Turing.

En ce qui concerne le degré de difficulté entre P et NP - il y a de bonnes raisons de penser que ce pourrait être au moins aussi difficile que la très vieille conjecture mathématique de Riemann (maintenant âgée de 1,5 siècle ), car les deux ont reçu le même prix de 1 M $ depuis plus de une décennie, et aucun n'a encore été résolu / premier.

En d'autres termes, définir précisément les algorithmes réellement "efficaces" est en fait l'un des problèmes ouverts les plus importants et les plus difficiles existants en sciences théoriques et en mathématiques .

En fait, la question de "ce qui est efficacement calculé" est en réalité encore plus subtile, car il existe une variante de la thèse de Church-Turing appelée thèse P-time CT, et on ne sait pas si l'informatique quantique la viole réellement . Avec le résultat décisif de Shor dans le domaine de la gestion de la qualité en temps réel, l’affacturage a été considéré comme une tournure dramatique dans cette recherche. En d’autres termes, le problème de ce qui est efficacement calculé s’applique de manière plausible aux principes de la physique profonde, et concerne le point de savoir si l’informatique quantique peut calculer plus efficacement que le calcul classique, qui est également un problème généralement ouvert dans les domaines de la théorie théorique et de la physique avancée.

On peut donc même ajouter que P vs NP et la question de l’efficacité de l’informatique peuvent revêtir une importance cruciale ou fondamentale en plus de la physique et des mathématiques et des mathématiques .

[1] Problème P vs NP, wikipedia

[2] Problèmes liés aux prix du millénaire

[3] Classe P / Poly, wikipedia

[4] algorithme de Shor

Les algorithmes de temps polynomiaux sont considérés comme efficaces uniquement par rapport au temps non polynomial le plus dur, en particulier le soi-disant NP-Complete. Voir l'image: Diagramme d'Euler pour les problèmes P, NP, NP complet et NP difficile .