Expliquer la théorie de la complexité informatique
https://stackoverflow.com/questions/308213
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
En supposant des connaissances en mathématiques, comment donneriez-vous un aperçu général de la théorie de la complexité de calcul au naïf?
Je cherche une explication à la question P = NP. Qu'est-ce que P? Qu'est-ce que le NP? Qu'est-ce qu'un NP-Hard?
Parfois, Wikipedia est écrit comme si le lecteur comprenait déjà tous les concepts en jeu.
La solution
Hoooo, flashback de doctorat. Ok, voilà.
Nous commençons par l’idée d’un problème de décision, problème pour lequel un algorithme peut toujours répondre "oui". ou " n ° " Nous avons également besoin de l’idée de deux modèles d’ordinateur (machine de Turing, vraiment): déterministe et non déterministe. Un ordinateur déterministe est l’ordinateur normal auquel nous pensons toujours; Un ordinateur non déterministe est un ordinateur semblable à celui auquel nous sommes habitués, à l'exception de son parallélisme illimité. Ainsi, chaque fois que vous vous rendez dans une succursale, vous créez un nouveau "processus". et examiner les deux côtés. Comme l’a dit Yogi Berra, lorsque vous arrivez à un embranchement, vous devriez le prendre.
Un problème de décision se trouve dans P s’il existe un algorithme polynomial connu permettant d’obtenir cette réponse. Un problème de décision est dans NP s’il existe un algorithme polynomial connu permettant à une machine non déterministe d’obtenir la réponse.
Les problèmes connus pour être dans P le sont trivialement dans NP --- la machine non déterministe ne se donne jamais la peine de se lancer dans un autre processus, et agit comme une solution déterministe. On sait que certains problèmes ne sont ni dans P ni dans NP; un exemple simple consiste à énumérer tous les vecteurs de bits de longueur n. Quoi qu'il en soit, cela prend 2 n étapes.
(Strictement, un problème de décision est dans NP si une machine non déterministe peut arriver à une réponse en temps réel, et une machine déterministe peut vérifier que la solution est correcte en temps réel.)
Mais il existe des problèmes connus pour être dans NP pour lesquels aucun algorithme déterministe multi-temps n'est connu; en d'autres termes, nous savons qu'ils sont en NP, mais nous ne savons pas s'ils sont en P. Y a-t-il un itinéraire qui couvre toutes les villes et qui retourne au point de départ, avec une distance inférieure à x ? C’est facile dans une machine non déterministe, car chaque fois qu’un vendeur ambulant non déterministe s’approche, il le prend: ses clones se dirigent vers la prochaine ville qu’ils n’ont pas visitée et, à la fin, ils comparent les notes et voient si l'un des clones a pris moins de x distance.
(Ensuite, beaucoup de clones exponentiellement doivent se battre pour savoir lesquels doivent être tués.)
On ne sait pas si Decision-TSP est dans P: il n'y a pas de solution multi-temps connue, mais il n'y a pas de preuve qu'une telle solution n'existe pas.
Maintenant, un autre concept: étant donné les problèmes de décision P et Q, si un algorithme peut transformer une solution pour P en une solution pour Q en temps polynomial, on dit que Q est poly-temps réductible (ou simplement réductible) à P.
Un problème est NP-complet si vous pouvez prouver (1) qu’il est dans NP et (2) montrer qu’il est poly-temps réductible à un problème déjà connu comme NP-complet. (Le plus difficile était de fournir le premier exemple de problème NP-complet: cela a été fait par Steve Cook dans Théorème de Cook .)
Donc, vraiment, cela dit que si quelqu'un trouve une solution multi-temps à un problème NP-complet, il en a automatiquement une pour tous les problèmes NP-complets; cela signifie également que P = NP.
Un problème est NP-difficile si et seulement si c'est "au moins comme". difficile comme un problème NP-complet. Le problème plus classique du vendeur ambulant qui consiste à trouver le trajet le plus court est NP-difficile, et non strictement NP-complet.
Autres conseils
La Introduction à la théorie de l'informatique est un excellent livre, très lisible. La Grande ressource de Scott Aarons est une autre excellente ressource Idées en informatique théorique .
Le formalisme utilisé consiste à examiner les problèmes de décision (problèmes avec une réponse Oui / Non, par exemple, "ce graphique a-t-il un cycle hamiltonien") en tant que "langues"? - ensembles de chaînes - entrées pour lesquelles la réponse est Oui. Il existe une notion formelle de ce qu’est un "ordinateur". est (machine de Turing), et il y a un problème en P s’il existe un algorithme polynomial de résolution de ce problème (étant donné une chaîne en entrée, dites Oui ou Non) sur une machine de Turing.
Il y a un problème dans NP s'il est vérifiable en temps polynomial, c'est-à-dire si, pour les entrées pour lesquelles la réponse est Oui, il existe un certificat (de taille polynomiale) qui permet de vérifier que le la réponse est oui en temps polynomial. [Par exemple. à partir d'un cycle hamiltonien, vous pouvez évidemment vérifier qu'il en est un.]
Cela ne dit rien sur la manière de trouver ce certificat. De toute évidence, vous pouvez essayer "tous les certificats possibles". mais cela peut prendre un temps exponentiel; il n'est pas clair si vous aurez toujours toujours plus que du temps polynomial pour décider Oui ou Non; Telle est la question P vs NP.
Un problème est difficile à résoudre si pouvoir résoudre ce problème signifie pouvoir résoudre tous les problèmes de NP.
Voir aussi cette question: Qu'est-ce qu'un NP-complete en informatique?
Mais en réalité, tout cela ne vous est probablement qu’ vague. il vaut la peine de prendre le temps de lire par exemple Le livre de Sipser. C'est une belle théorie.
Ceci est un commentaire sur le message de Charlie.
Un problème est NP-complet si vous pouvez prouver que (1) il est en NP et (2) montrer qu’il est poly-temps réductible à un problème déjà connu de être NP-complet.
Il y a une erreur subtile avec la deuxième condition. En fait, vous devez prouver qu’un problème connu de NP-complete (disons Y ) peut être réduit en temps polynomial à ce problème (appelons-le problème X ).
Le raisonnement derrière cette preuve est que si vous pouviez réduire un problème complet avec NP à ce problème et réussir à le résoudre en plusieurs fois, alors vous avez également réussi à le résoudre. trouver une solution multi-temps au problème complet NP , ce qui serait une chose remarquable (voire impossible), car vous aurez ainsi réussi à résoudre le problème de longue date P = NP problème.
Une autre façon d’examiner cette preuve consiste à la considérer comme utilisant la technique de la preuve contre-positive, qui stipule essentiellement que si Y - > X , puis ~ X - > ~ Y . En d’autres termes, ne pas être en mesure de résoudre Y en temps polynomial n’est pas possible, c’est ne pas être en mesure de résoudre X en temps poly-temps non plus. D'un autre côté, si vous pouviez résoudre X en poly-time, vous pourriez également résoudre Y en poly-time. De plus, vous pouvez résoudre tous les problèmes qui se réduisent à Y en temps multiple ainsi que la transitivité.
J'espère que mon explication ci-dessus est suffisamment claire. Une bonne source est le chapitre 8 de la Conception d’algorithme de Kleinberg et Tardos ou le chapitre 34 de Cormen et al.
Malheureusement, les deux meilleurs livres que je connaisse ( Garey et Johnson et Hopcroft et Ullman ) démarrent tous deux au niveau de la gestion des études supérieures mathématiques. Cela est presque certainement nécessaire, car il est très facile de mal comprendre ou de mal interpréter le problème. Jeff a failli se faire couper les oreilles lorsqu'il a tenté de saisir la question trop Folksy / jokey un ton.
La meilleure solution consiste peut-être simplement à effectuer de nombreux travaux pratiques avec la notation big-O en utilisant de nombreux exemples et exercices . Voir aussi cette réponse . Notez cependant que ce n'est pas tout à fait la même chose: des algorithmes individuels peuvent être décrits par des asymptotes, mais dire qu'un problème est d'une certaine complexité est une affirmation sur tous les algorithmes possibles pour cela. C'est pourquoi les preuves sont si compliquées!
Je me souviens de "Complexité informatique". de Papadimitriou (j'espère avoir bien orthographié le nom) comme un bon livre
Très simplifié: Un problème est difficile à résoudre si la seule façon de le résoudre consiste à énumérer toutes les réponses possibles et à les vérifier toutes.
Voici quelques liens sur le sujet:
Si vous connaissez bien l'idée de cardinalité d'ensemble, c'est-à-dire le nombre d'éléments d'un ensemble, vous pouvez alors afficher la question telle que P représentant la cardinalité des nombres entiers, alors que NP est un mystère: plus gros comme la cardinalité de tous les nombres réels?
Ma réponse simplifiée serait: "La complexité informatique est l’analyse de la difficulté d’un problème à résoudre lorsque vous ajoutez plus d’éléments."
Dans cette phrase, le mot "plus difficile" est délibérément vague car il peut faire référence au temps de traitement ou à l'utilisation de la mémoire.
En informatique, il ne suffit pas de pouvoir résoudre un problème. Il doit pouvoir être résolu dans un délai raisonnable. Ainsi, alors que dans les mathématiques pures, vous trouvez une équation, dans CS, vous devez affiner cette équation afin de pouvoir résoudre un problème en un temps raisonnable.
C’est la façon la plus simple de le dire, c’est peut-être trop simple pour vos besoins.
Selon votre temps, il serait peut-être préférable de commencer par DFA, NDFA, puis de montrer qu'ils sont équivalents. Ensuite, ils comprendront ND vs. D, et comprendront beaucoup mieux les expressions régulières comme un effet secondaire intéressant.
