Pourquoi les problèmes NP appelé de cette façon (et NP-dur et NP-complet)?

Question

Vraiment .. Je vais avoir le dernier test pour l'obtention du diplôme ce mardi, et c'est l'une des choses que je viens ne pouvais comprendre. Je me rends compte qu'une solution pour le problème NP peut être verfied en temps polynomial. Mais qu'est-ce que le déterminisme doit faire avec ça?
Et si vous pouviez me dire où NP-complet et NP-dur a obtenu leur nom, ce serait génial (je suis sûr que je reçois le sens d'eux, je ne vois pas ce que leurs noms ont à voir avec ce qu'ils sont).
Désolé si c'est trivial, je ne peux pas sembler l'obtenir (-:
Merci à tous!

Answer 1

P

Classe de tous les problèmes qui peuvent être résolus par une machine de Turing déterministe dans le temps polynomiale.

NP

Classe de tous les problèmes qui peuvent être résolus par une machine Turing non déterministe dans le temps polynomiale (ils peuvent aussi être vérifiés par une machine de Turing déterministe dans le temps polynomiale. )

NP-dur

Une classe de problèmes qui sont « au moins aussi dur que les problèmes les plus difficiles dans NP ». Formellement, un problème est NP-difficile ssi il y a un problème NP-complet qui est polynomiale Turing réductible; (Aussi: ssi il peut être résolu en temps polynomial par une machine oracle avec un oracle pour le problème). Il est assez évident où le nom vient.

NPC

La classe de problèmes qui sont à la fois NP, ainsi que NP-Hard. En ce qui concerne la désignation, même wikipedia ne sait pas pourquoi il est nommé comme il est.

Answer 2

Commençons avec Let "non déterministes". Une machine déterministe peut être dans un état à la fois. Nous pouvons réellement faire eux. Une machine non déterministe est une construction théorique qui peut être dans plus d'un état à la fois. (Il y a des similitudes avec l'informatique quantique, mais pour nos fins ici, ils sont trompeurs. Pas en tenir compte.)

Si nous voulons résoudre un problème avec une machine déterministe, on commence vers le haut, et il passe par une série d'étapes pour essayer de trouver un problème. Si l'on modèle à l'aide d'une machine non déterministe, il peut passer par toutes les séries de mesures possibles en même temps.

L'ensemble des problèmes que nous allons être concernés par des problèmes est de décision: étant donné un énoncé de problème, il y a une solution ou non. Trouver une solution ou un rapport qu'il n'y en a pas. Par exemple, supposons que vous avez un ensemble d'instructions logiques: A ou non-B, B ou C ou D, D ou A ou B, .... Étant donné un ensemble arbitraire, vous pouvez trouver des valeurs de vérité pour toutes les variables de telle sorte que toutes les déclarations sont vraies?

Maintenant, considérons le P. Supposons que nous représentons la taille d'un problème en n. La taille pourrait être le nombre de villes dans un problème du voyageur de commerce, le nombre de déclarations logiques dans le problème ci-dessus, peu importe. Compte tenu d'un certain n, le problème, il faudra une certaine quantité de ressources pour résoudre un système donné. Maintenant, si l'on double les ressources ou la capacité de calcul, ce qui arrive à la taille du problème que nous pouvons résoudre? Si le problème est de complexité polynomiale, ce qui signifie en P, la taille va par une certaine fraction. Il pourrait doubler ou augmenter de 40%, ou 10%. En revanche, si elle est d'une complexité exponentielle, la taille va par un certain nombre. Nous pensons généralement des problèmes P comme des problèmes résoluble et exponentielle que les problèmes insolubles obtenir de grandes, bien que ce soit une simplification. D'un point de vue informel, la complexité polynomiale est d'être en mesure de choses à comprendre le problème de manière séquentielle, alors que exponentielle est d'avoir à regarder toutes les combinaisons possibles.

Supposons que nous pouvons résoudre le problème en temps polynomial sur une machine déterministe. Le problème est dans P. Supposons que nous pouvons résoudre en temps polynomial sur une machine non déterministe, qui est la même chose que d'être en mesure de vérifier une solution proposée en temps polynomial sur une machine déterministe. Ensuite, le problème est dans NP. L'astuce ici est que nous ne pouvons pas faire de véritables machines non déterministes, de sorte que le fait qu'un problème est dans NP ne signifie pas qu'il est pratique de résoudre.

à NP-complet. Tous les problèmes de P sont NP. Pour les problèmes A et B NP, nous pourrions être en mesure de dire que si A est dans P, donc est B. Cela se fait en trouvant un moyen de retraiter B comme une sorte de problème. Un problème NP-complet est un tel que, si elle est en P, tous les problèmes de NP est en P. Comme vous pouvez le deviner, trouver un moyen de retraiter tous les problèmes possibles comme l'un d'un particulier n'a pas été facile, et je vais juste dire que le problème avec les états logiques ci-dessus (le problème satisfiabilité) a été le premier prouvé NP-complet. Après cela, il était plus facile, car il est seulement nécessaire de prouver que si le problème C était en P, donc était Satisfiabilité.

On croit généralement qu'il ya des problèmes qui sont NP mais pas P, et une preuve a été récemment publiée (qui peut ou peut ne pas se révéler valide). Dans ce cas, les programmes NP-complets sont les plus difficiles sortes de problèmes dans NP.

Il y a des problèmes qui ne rentrent pas dans ce moule. Le VRP problème, comme normalement posé, est de trouver le meilleur itinéraire reliant toutes les villes. Ce n'est pas un problème de décision, et nous ne pouvons pas vérifier directement toute solution proposée. Nous pouvons reformuler comme un problème de décision: étant donné un coût C, est-il une route qui est moins cher que C? Ce problème est NP-complet, et avec un peu de travail, nous pouvons résoudre le TSP d'origine aussi facilement que modifié, NP-complet, sous forme. Par conséquent, le TSP est NP-dur, car ilEst au moins aussi dur comme un problème NP-complet.

Answer 3

NP est appelé NP (temps polynôme non déterministes), car un problème NP peut être résolu en temps polynomial par une machine de Turing non déterministes.

Answer 4

Commençons par NP: dans NP, N est pour « non déterministes » et P est pour « polynomial ». Il est la classe des problèmes qui peuvent être résolus en temps polynomial si vous avez une machine de Turing non déterministes qui peut se ramifier à chaque cycle d'explorer les possibilités en parallèle (la « verify la solution » définition alternative est devenue récemment populaire, mais il ne dit pas clairement ce que signifie "N"). La machine non déterministe peut être comparé à un ordinateur parallèle avec un nombre infini de processeurs, et la capacité de fork() à chaque instruction.

Dire qu'un problème est Q signifie « NP-dur » que tout problème de NP peut être réduite à problème Q (en temps polynomial). Étant donné que la relation « peut être réduit à » entre les problèmes est une relation d'ordre, vous pouvez penser « NP-dur » comme signifiant « au moins aussi dur que tous les problèmes NP ».

Un problème « NP-complet » est tout simplement l'un des problèmes de NP qui est NP-dur. Je suppose que la classe de problèmes avait besoin d'un nom, mais je ne suis pas sûr de savoir comment expliquer le choix du mot « complet ».

Answer 5

  

Mais qu'est-ce que le déterminisme doit faire avec cela?

De Wikipedia :

NP est l'ensemble de tous les problèmes de décision pour lesquels les « réponses de yes'-ont des preuves vérifiables de manière efficace du fait que la réponse est en effet « oui ». Plus précisément, ces preuves doivent être vérifiables en temps polynomial par une machine de Turing déterministe

Je ne sais pas sur l'histoire des noms cependant. EDIT: J'ai devine cependant. Ce qui suit est la spéculation, mais je ne pense pas qu'il soit déraisonnable.

NP-dur est un problème qui est au moins aussi dur que les problèmes les plus difficiles dans NP. Par conséquent, on pourrait dire que le problème en question aurait la dureté NP., Donc NP-dur.

Si un problème unique NP-complet peut être résolu rapidement, tous les problèmes de NP peut également être résolu rapidement. Par conséquent, l'ensemble complet des problèmes NP pourrait être résolu.

EDIT2 : Complete (complexité) Wikipedia article indique:

  

un problème de calcul est complet pour une classe de complexité si elle est, dans un sens formel, l'un des plus « durs » ou « le plus expressif » problèmes dans la classe de complexité