human
Qu'est-ce que P vs NP et comment une solution pourrait-elle bénéficier à l'informatique ? ELI5 : Qu'est-ce que P vs NP et comment une solution pourrait-elle bénéficier à l'informatique ? S'il vous plaît, expliquez-moi comme si j'avais cinq ans.
gpt
* * P * * et * * NP * * sont des classes de problèmes de décision et le problème * * P = NP * * demande s'ils sont identiques . Un * problème de décision * est une question oui-non qui dépend d'une sorte d'entrée ; par exemple " Cette carte de dragueur de mines est-elle valide ? (c'est-à-dire qu'il y a une configuration de mines qui est cohérente avec la carte) ", où l'entrée est une carte de dragueur de mines. Notez que « décider » d'un problème de décision signifie « déterminer la réponse à ». Notez également que même si la plupart des discussions ici porteront sur les problèmes de décision, les questions qui ne sont pas oui-non (par exemple "Quels mouvements corrects garantis puis-je faire sur ce plateau de dragueur de mines ?") peuvent souvent être exprimées en demandant plusieurs oui-non. pas de questions ( laissées en exercice au lecteur pour cet exemple particulier ) . Les problèmes qui sont dans * * P * * sont considérés * efficacement décidables * , ce qui signifie grossièrement que nous pouvons écrire un programme pour répondre définitivement oui ou non, ce qui prendrait un temps raisonnable sur des entrées de taille raisonnable ( Note technique : Ce n'est pas vraiment vrai Dans ce domaine de la science informatique , efficace signifie temps polynomial , qui pourrait avoir même de minuscules entrées de problèmes comme prendre des millénaires à résoudre ou plus sur les ordinateurs actuels ) . Un exemple de problème est : « Etant donné un tableau des taux de conversion des devises, pouvez-vous convertir de l'argent d'une devise donnée vers différentes devises et vous retrouver avec plus d'argent que vous n'en aviez au départ ? » ; un ordinateur serait capable de répondre à cette question pour une table avec des dizaines de milliers de devises. Un autre exemple de problème ici est : " Etant donné une liste de nombres , tous les éléments sont - ils uniques ? " ; un ordinateur pourrait en décider pour une liste de milliards de nombres. Probablement la définition la plus simple pour * * NP * * est que lorsqu'un problème est dans * * NP * * , les réponses oui peuvent être * efficacement vérifiées * (c'est-à-dire que la vérification des réponses oui est dans * * P * * ). Considérez les trois exemples précédents : - Cohérence du démineur - si la réponse est oui, alors il y a une configuration de mines qui est cohérente avec le tableau, et étant donné une telle configuration, nous pouvons vérifier efficacement (et facilement) que le tableau est valide et donc la réponse est oui. - Arbitrage de devises - Si la réponse est oui, alors il existe une liste ordonnée de conversions de devises qui profite, et étant donné une telle liste ordonnée, nous pouvons vérifier efficacement que nous pouvons en tirer profit et donc la réponse est oui. - Unicité de l'élément - Si la réponse est non, alors il y a un nombre qui apparaît plusieurs fois dans la liste, et étant donné un tel nombre, nous pouvons vérifier efficacement que la réponse est non. Donc, pour les exemples ici, il y a une notion de "vérification" facile à voir. Les deux premiers exemples ont des réponses "oui" aussi facilement vérifiables (ce qui signifie qu'elles sont en **NP**), et le troisième a des réponses "non" aussi facilement vérifiables (ce qui signifie qu'elles sont en **co-NP**). Nous appelons normalement les informations utilisées pour la vérification ( configuration des mines , etc . ) un * certificat * . En fait, il s'avère que le troisième problème est également dans * * NP * * . Si la réponse pour une entrée donnée est oui , nous pouvons prendre un certificat vide et toujours vérifier efficacement que la réponse est oui ( puisque la décision du problème est dans * * P * * ) . En conséquence , chaque problème dans * * P * * est également dans * * NP * * ( et * * co - NP * * ) . Donc quand un problème est dans * * NP * * , il existe un * vérificateur * efficace pour le problème . Ce vérificateur prend en entrée à la fois l'entrée du problème d'origine et un certificat. Pour chaque entrée originale où la réponse est oui , il existe un certificat qui fait dire oui au vérificateur . Pour chaque entrée d'origine où la réponse est non, il n'y a pas de certificat qui oblige le vérificateur à dire oui. ( Note technique : Pour le cas oui , nous exigeons que le certificat soit au plus polynomialement plus grand que l' entrée d' origine ) . Donc le problème * * P = NP * * demande si ces deux classes sont égales . C'est sans doute le plus gros problème ouvert en informatique (nous cherchons toujours le moyen le plus rapide de multiplier deux nombres, mais c'est à quelqu'un d'autre d'en parler). Fondamentalement, toutes les techniques de preuve dans ce domaine de l'informatique (par exemple la relativisation, l'algébrisation) se sont révélées inutiles pour attaquer ce problème. Si * * P = NP * * , alors étant donné un problème que nous pouvons vérifier efficacement , nous pouvons aussi le décider efficacement . Cependant , notant la mise en garde précédente sur ce que signifie " efficace " , cela pourrait n'avoir aucune implication pratique . S'il s'avérait que cela ait des implications pratiques, les logiciels de logistique à travers le monde commenceraient à générer de meilleures solutions et de nombreux problèmes mathématiques non résolus deviendraient faciles pour les ordinateurs. Cela signifiera également qu'il y aurait des algorithmes efficaces pour casser les cryptosystèmes les plus courants ! Quelle que soit la manière dont le problème * * P = NP * * est résolu , il représentera probablement une avancée considérable pour l' informatique théorique . Toute résolution du problème nous aidera probablement aussi à progresser sur d'autres problèmes non résolus de la théorie de la complexité computationnelle (par exemple, NC = P, P = BPP, L = NL, etc.).