Pourquoi le temps polynôme est appelé « efficace »?

Question

Pourquoi la science informatique toute la complexité qui est au plus polynomiale est considéré comme efficace?

Pour toute application pratique ^(a) , algorithmes avec $ complexité n ^ {\ log n} $ sont beaucoup plus rapides que les algorithmes qui fonctionnent dans le temps, disons, n $ ^ {80} $, mais la première est considérée comme inefficace alors que celui-ci est efficace. Où est la logique?!

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

Answer 1

Une autre perspective sur « efficacité » est que le temps polynomiale permet de définir une notion d ' « efficacité » qui ne dépend pas de modèles de machines. Plus précisément, il existe une variante de la thèse Church-Turing appelée « efficace Church-Turing thèse » qui dit que tout problème qui fonctionne en temps polynomiale sur le type de modèle de machine également fonctionner en temps polynomial sur un autre modèle de machine tout aussi puissante.

Ceci est une déclaration plus faible à la thèse générale de CT, et est « sorte de » violé par les deux algorithmes probabilistes et algorithmes quantiques, mais n'a pas été violé dans le sens d'être en mesure de résoudre un problème NP-dur en poly le temps en changeant le modèle de la machine.

est en fin de compte la raison pour laquelle le temps polynôme est une notion populaire dans theoryCS. Cependant, la plupart des gens se rendent compte que cela ne reflète pas « l'efficacité pratique ». Pour en savoir plus, le poste de Dick Lipton sur « galactiques algorithmes » est une excellente lecture.

Answer 2

En théorie, nous nous occupons du comportement asymptotique et décrire des classes de problèmes et des algorithmes basés sur leur comportement asymptotique. Le mot-clé ici est asymptotique . $ O (n ^ {80}) $ est plus rapide que $ O (n ^ {\ log n}) $ asymptotiquement, soit à partir de $ n> 1208925819614629174706176 $ (qui, par la voie est appelée: septillion), unité en supposant coefficients constants, et pas de termes d'ordre faible.

Dans la pratique, toutefois, l'attention est portée à la fois des exposants et des coefficients constants. Dans les pratiques, les tailles d'entrée ne peuvent pas croître à quatrillions, donc, oui, n $ ^ {\ log n} $ à toutes fins utiles sera un choix supérieur à n $ ^ {80} $. D'autres facteurs sont aussi importants dans les pratiques:. Parallélisme, les modèles d'accès mémoire (par exemple localité)

Par exemple, la plupart des bibliothèques pour la multiplication entier, par exemple GMP mettra en œuvre un mélange d'algorithmes et sélectionner l'algorithme inférieur en fonction de la taille d'entrée sélectionnez la pratiquement algorithmes supérieurs en fonction de la taille d'entrée, bien que ces algorithmes pourraient être asymptotiquement inférieurs. Certains algorithmes asymptotiquement « inférieurs » sera plus rapide sur certaines tailles d'entrée et seront sélectionnés sur les algorithmes optimaux.

Un autre exemple, l'algorithme de multiplication de la matrice la plus rapide connue est Chaudronnier-Winograd algorithme qui fonctionne en $ O (n ^ {2,3737}) $ (il y a des améliorations récentes, plus ). Cependant, il n'a jamais été mis en œuvre parce que (1) il est difficile (2), le coefficient constant est gigantesque. Tous les paquets d'algèbre linéaire utilisent moins optimale de Strassen .

TL;. Soins de la théorie DR pour le comportement asymptotique afin de comparer les algorithmes comme la limite de taille d'entrée passe à des nombres arbitrairement grands

Answer 3

Cette réponse se penchera sur le contexte « plus d'image » de votre question. la science informatique est en fait une science relativement jeune et un peu ouvert et il n'a pas encore de grandes ou même de bonnes réponses à certaines questions fondamentales et fondamentales. La question de base "ce qui est efficace calculée" est soit avec précision ou à peu près formalisé dans CS (selon l'opinion) comme le célèbre P vs problème NP (ou P étroitement liés vs EXPTIME problème), et son encore open après plus de quatre décennies d'être initialement introduit par Cook / Levin ~ 1970 et le travail intense par les mondes plus grands informaticiens (et de nombreux mathématiciens sont également intéressés par le problème fondamentale).

En d'autres termes, même avec rough définition de « efficace » que le temps de P, et l'un des prix scientifiques d'une valeur plus élevée - à savoir prix 1 M $ attaché au problème pour plus de 10ans - ordinateur la science ne peut pas prouver même que certains problèmes (près de cette frontière) doivent ou ne doivent pas avoir des algorithmes efficaces (pTIME). Par conséquent, la définition exacte de « efficace » du temps plus précis que P n'est pas nécessaire ou même possible à ce moment. Si / quand la conjecture P vs NP est réglé d'une façon ou l'autre, une définition plus stricte de « efficace » peut ou vraisemblablement sera possible.

De plus, on pourrait se sentir que la définition Ptime de « efficace » pourrait même être un peu « bâclée », et la plupart des informaticiens serait probablement d'accord, et presque tous d'entre eux pensent P vs conjecture NP est d'une importance capitale pour détermination, au point qu'ils pourraient même considérer cette affirmation ou observation comme trivial .... autrement dit, pour ainsi dire, est un travail en cours / nous y travaillons . (En fait des informaticiens grand public vont même jusqu'à, ne plaisantant qu'à moitié, de se référer systématiquement à l'écart et le manque de progrès / séparations définitives comme embarrassant ).

En fait, il y a même un étroitement lié / significativement plus forte conjecture que P vs NP, à savoir NP vs P / poly, qui ne peut être résolu que par la science informatique à cette époque. il conjecture que problèmes NP-temps ne peuvent pas être résolus par any circuits « P-taille », à savoir même pas limité à ces circuits qui peuvent être créés par des algorithmes / machines de Turing.

En ce qui concerne à quel point P vs NP peut être - il y a une raison solide de penser qu'il peut être au moins aussi dur comme très ancienne conjecture de Riemann en mathématiques (maintenant 1,5 siècle vieux), parce que les deux ont eu le même prix de 1 M $ pour plus d'une décennie, et aucun d'eux n'a encore été résolu / premier.

En d'autres termes, de définir précisément ce que les algorithmes sont vraiment « efficace » est en fait l'un des les plus importants et les plus durement existants problèmes ouverts dans les sciences et les mathématiques théoriques .

En fait, la question de « ce qui est efficace calculée » est en fait encore plus subtile, parce qu'il est une variante de la thèse Church-Turing appelée la thèse de CT P-temps, et on ne sait pas si l'informatique quantique en fait viole il. Avec le résultat de la percée de Shor de QM P-temps, l'affacturage considéré comme une torsion dramatique dans cette recherche. En d'autres termes, le problème de ce qui est efficace calculée en fait descend de manière plausible jusqu'aux principes de la physique profonde, et est de savoir si le calcul quantique peut calculer de manière plus efficace que le calcul classique, qui est aussi un problème généralement ouvert dans CS théorique et la physique de pointe.

Alors on peut même ajouter que P vs NP et la question de l'informatique efficace peut être d'une importance cruciale ou fondamentale dans - plus de CS et de mathématiques -. physique

[1] P vs problème NP, wikipedia

[2] problèmes de prix Millenium

[3] P / classe Poly, wikipedia

[4] algorithme de Shor

Answer 4

algorithmes polynomiaux sont considérés comme efficaces que par rapport au temps le plus dur non polynomiale en particulier que l'on appelle NP-complet. Voir l'image: diagramme d'Euler P, NP, NP-complet, et NP-dur ensemble de problèmes .