P= clarification np

Question

Utilisez le vendeur de voyage comme exemple, sauf si vous pensez qu'il y a un exemple plus simple et plus exemplaire.

Ma compréhension de la question P= NP est que, étant donné la solution optimale d'un problème difficile, il est facile de vérifier la réponse, mais très difficile à trouver la solution.

Avec le vendeur itinérant, compte tenu de la route la plus courte, il est tout aussi difficile de déterminer que c'est la voie la plus courte, car vous devez calculer chaque voie pour vous assurer que la solution est optimale.

Cela n'a pas de sens.Alors, que manque-t-il?J'imagine que beaucoup d'autres personnes rencontrent une erreur similaire dans leur compréhension lorsqu'elles apprennent à ce sujet.

Answer 1

Votre version du TSP est en réalité np-dur, exactement pour les raisons que vous indiquez.Il est difficile de vérifier que c'est la solution correcte.La version du TSP qui est NP-complète est la version de décision du problème (citant Wikipedia):

La version de décision du TSP (lorsque la tâche a donné une longueur L, la tâche est de décider si le graphique aUne visite au plus l) appartient à la classe de problèmes complets NP.

En d'autres termes, au lieu de demander "Quel est le itinéraire le plus court possible via le graphique de TSP?", nous demandons "y a-t-il une route via le graphique à TSP qui correspond à mon budget?".

Answer 2

Il y a beaucoup de réponses décentes ici, mais rien n'empêche quelques malentendus assez importants que vous semblez avoir.

P et NP sont des cours de ce que l'on appelle des "problèmes de décision". Ce sont des problèmes dont la réponse est oui ou non. (Plus de formellement, ils sont toutes des questions à donner une chaîne et une langue, est la chaîne dans la langue mais qui n'est pas une distinction importante). En ce sens, vous êtes légèrement incorrect dans votre compréhension lorsque vous dites "Compte tenu de la solution optimale d'un problème difficile, il est facile de vérifier la réponse, mais très difficile à trouver la solution" car les problèmes de décision n'ont pas "des solutions optimales. " Les problèmes où des solutions peuvent être "évaluées" et que vous recherchez la "meilleure" solution sont des problèmes d'optimisation, dont le problème du vendeur itinérant est un exemple. Vous pouvez toujours transformer un problème d'optimisation en un problème de décision en examinant le problème "donné une instance de ce problème d'optimisation et un entier K, le problème a-t-il une solution dont la valeur objective est meilleure que k?".

Une autre chose est que vous pourriez être légèrement confus quant à ce que NP signifie. P est la classe de problèmes de décision pouvant être résolue en temps polynomial (que vous semblez comprendre). NP signifie "temps polynôme non déterministe" et c'est la classe de problèmes que vous pouvez facilement vérifier si une instance du problème devrait donner une réponse oui donnée des informations supplémentaires. Donc, regarder notre problème de TSP, si j'ai une instance de TSP, et une solution dont le coût total est inférieur à k, je peux facilement vérifier que la solution est vraiment une solution et que son coût est inférieur à k. Donc, le problème de décision associé à la TSP est dans NP. Mais tous les problèmes de NP ne sont pas "difficiles". En fait, p est un sous-ensemble de NP car si vous pouvez facilement résoudre le problème de décision, vous pouvez facilement vérifier si une instance vous donne une réponse oui en résolvant simplement cela.

Mais il y a des problèmes dans NP que nous pensons être difficiles à résoudre. À la simplification d'un peu, nous appelons ces problèmes de NP-Complets. (Notez que ceux-ci doivent toujours être des problèmes de décision). Nous pouvons dire un problème A est au moins aussi acharné que le problème B Si, nous supposons que nous avons une blackbox oracle qui résout le problème A et que nous pouvons l'utiliser pour résoudre efficacement le problème B. Regardons à nouveau l'exemple de TSP. Clairement, si vous pouviez résoudre le problème d'optimisation (la solution optimale), vous pouvez résoudre le problème de décision. Le problème d'optimisation est donc au moins aussi acharné que son problème de décision correspondant. Si nous avons montré que la version de décision du TSP était NP-complète (ce qu'elle est), nous saurions que le problème d'optimisation TSP est également aussi acharné que les problèmes de NP-complets, mais cela n'est pas réellement NP-complet car il ne s'agit pas 'T un problème de décision. Nous appelons de tels problèmes np-dur.

Answer 3

$ p $ et $ np $ sont des catégories de problèmes de décision. Le résultat d'un algorithme pour un problème de décision est soit «oui» ou «non». Même pour un problème dans $ p $ , une telle réponse ne peut pas conduire à une vérification rapide.

Une instance de la version de décision du TSP est "Compte tenu d'une collection de villes et de distances interurbaines, y a-t-il une tournée avec une longueur totale inférieure à $ k $ ? ", où $ k $ est une constante spécifiée dans l'instance. Le résultat est "oui" ou "non". Dans aucun cas, la réponse n'a conduit à une vérification rapide de l'exactitude de la réponse.

La promesse que vous posez sur ce sujet est la suivante: Étant donné une visite proposée particulière, on peut en temps polynôme:

• Déterminez que la visite proposée est en fait une visite - visite toutes les villes et ne traverse que des itinéraires interurbains qui existent (parfois "qui ont des distances finies" quand on code les voies manquantes comme ayant une longueur $ \ \ € $ ).
• Si tel est le cas, déterminez que la longueur de la route est plus courte que la constante $ K $ dans l'instance de problème.

Ni une réponse de "oui" ou "non" fournit une visite proposée.

la valeur du modèle de $ np $ que vous utilisez est qu'il code un moyen pour faire un solveur: pour chaque Visite possible (typiquement un ensemble de manière exponentielle à itérer sur) vérifier si c'est une visite et si sa longueur est $ . Si oui, signalez "oui". Si nous épuisons la collection de visites possibles sans signaler "oui", signalez "Non".

Notez que ce modèle suggère que la difficulté de la solution rapide est pas que la vérification des conditions prend beaucoup de temps. La difficulté de la solution rapide est qu'il y a trop de visites potentielles à la recherche. Donc, si nous pouvions trouver un peu vraiment, vraiment intelligent de restreindre notre recherche à un minuscule sous-ensemble, la collection de visites potentielles, nous aurions une solution rapide pour une $ np $ Problème.

Recherche binaire dans une liste triée est un exemple où l'on a un moyen intelligent de rechercher dans la liste en évaluant uniquement les comparaisons de logarithmiquement (dans la longueur de la liste) plutôt que de nombreuses comparaisons. De ce point de vue, le problème du TSP est difficile, car nous ne connaissons pas une manière sensiblement plus rapide de rechercher dans les circuits proposés de chaque instance possible de problèmes de TSP.

Answer 4

NP est tout sur les problèmes de décision - problèmes où la réponse est "oui" ou "non".

Un problème est dans NP si pour chaque instance où la réponse est "oui", il y a un indice qui vous permet de prouver facilement que la réponse est "oui". Cela ne dit rien des instances où la réponse est "non". Ils peuvent être difficiles à résoudre.

Le problème de vendeur de voyage classique est le problème: donné un ensemble de villes et de leurs distances, est-il possible de trouver une tournée plus courte que k? Et bien évidemment, si la réponse est oui, une telle tournée existe et nous pouvons l'utiliser comme indice pour montrer facilement la réponse est oui. Si la réponse est non, personne n'a encore été trouvé avec aucun indice qui vous laisserait prouver que.

Vous avez indiqué un problème que vous avez également appelé "vendeur de voyage", mais c'est en fait différent. Vous demandez: Étant donné un ensemble de villes et de leurs distances et une tournée, est-ce la tournée la plus courte tour? Dans ce cas, si la réponse est "non", il y a une tournée plus courte, et nous pouvons l'utiliser comme indice pour montrer facilement la réponse est "non". C'est exactement le contraire de NP: votre version alternative du problème du vendeur itinérant est l'une pour chaque instance où la réponse est "non", il y a un indice qui vous permet de prouver facilement la réponse est "non". Parce que c'est le contraire exact de NP, cette classe s'appelle "CO-NP".

Il y a beaucoup de problèmes comme ça. Pour chaque problème dans NP, vous pouvez poser la question suivante: "La réponse de cette instance du problème" NO "" ", et bien sûr, la réponse est exactement le contraire du problème initial. Vous venez de faire l'erreur de penser que chaque problème avec les mots «voyager» et «vendeur» est le même problème.

Answer 5

Je trouve le plus facile à comprendre en utilisant le problème 3-sat NP-complet Problème:

Il y a N $ N $ variables booléennes et vous pouvez décider que chacun d'entre eux soit à régler la $ true $ ou $ false $ la valeur et vous êtes donné $ K $ clauses. Chacune des clauses contient 3 variables et les contraintes d'eux, comme $ (vrai ou faux ou faux) $ , de sorte que les Clauese seraient satisfaits si la première variable a été définie. à la vraie ou la deuxième variable à fausse ou la troisième variable à vrai. La $ K $ klauses peut contenir toutes les combinaisons possibles de trois des trois $ n $ variables et vous devez Décidez de quelle valeur chaque variable doit être définie pour que toutes les clauses soient satisfaites.

Si vous trouvez une combinaison de valeurs pour toutes les variables, de sorte que chaque clause est satisfaite, votre combinaison peut être vermentale très facile en allant juste une fois à la fois de la clause et de le tester, mais il peut être très difficile de trouver une combinaison qui satisfait à chaque clause.