- Le Problème
- La Solution
- Résumé
Si vous passez du temps dans ou autour de la programmation communautaire, vous avez probablement entendu le terme « P versus NP” assez fréquemment. Malheureusement, même beaucoup avec une formation formelle en informatique ont une faible compréhension du concept.
Voici donc une explication simple et concise:
le problème
p vs. NP le problème P vs. NP demande si chaque problème dont la solution peut être rapidement vérifiée par un ordinateur peut également être rapidement résolu par un ordinateur., (Wikipedia)
voyons donc ce que nous entendons par P et NP.
Les problèmes P sont facilement résolus par les ordinateurs, et les problèmes NP ne sont pas faciles à résoudre, mais si vous présentez une solution potentielle, il est facile de vérifier si elle est correcte ou non.
comme vous pouvez le voir sur le diagramme ci-dessus, tous les problèmes P sont des problèmes NP. Autrement dit, s’il est facile pour l’ordinateur de résoudre, il est facile de vérifier la solution. Donc, le problème P vs NP demande simplement si ces deux types de problèmes sont les mêmes, ou s’ils sont différents, c’est-à-dire qu’il y a des problèmes qui sont facilement vérifiés mais pas facilement résolus.,
Il semble actuellement que P NP NP, ce qui signifie que nous avons beaucoup d’exemples de problèmes auxquels nous pouvons rapidement vérifier les réponses potentielles, mais que nous ne pouvons pas résoudre rapidement. Regardons quelques exemples:
- Un voyageur veut visiter 100 villes différentes, en conduite, en commençant et se terminant son voyage à la maison. Il a un approvisionnement limité en essence, il ne peut donc parcourir qu’un total de 10 000 kilomètres. Il veut savoir si il peut visiter toutes les villes sans manquer d’essence., (de Wikipedia)
- Un agriculteur veut prendre 100 pastèques de différentes masses sur le marché. Elle doit emballer les pastèques dans des boîtes. Chaque boîte ne peut contenir que 20 kilogrammes sans se casser. L’agriculteur doit savoir si 10 boîtes lui suffiront pour transporter les 100 pastèques sur le marché. (de Wikipedia)
tous ces problèmes partagent une caractéristique commune qui est la clé pour comprendre L’intrigue de P versus NP: pour les résoudre, vous devez essayer toutes les combinaisons.
La Solution
C’est pourquoi la réponse à la P vs, Le problème NP est si intéressant pour les gens. Si quelqu’un était capable de montrer que P est égal à NP, cela rendrait les problèmes réels difficiles triviaux pour les ordinateurs.
résumé
- P vs. NP traite de l’écart entre les ordinateurs capables de résoudre rapidement les problèmes et simplement de tester les solutions proposées pour l’exactitude.
- En tant que tel, le problème P contre NP est la recherche d’un moyen de résoudre des problèmes qui nécessitent d’essayer des millions, des milliards ou des milliards de combinaisons sans avoir à essayer chacune d’elles.,
- résoudre ce problème aurait des effets profonds sur l’informatique, et donc sur notre société.
7 février 2017 — ajout des attributions Wikipédia.
Mars 2, 2014-nettoyé une partie de l’explication pour éviter la confusion.