Pas une question de programmation «pure», mais comme elle est profondément impliquée dans la théorie de la programmation, je pensais qu'il est préférable de demander ici.
Concernant le problème P NP, cet extrait de http://fr.wikipedia.org/wiki/ P_versus_np_problem : "En substance, la question p = np? Demande: supposons que oui réponses à une question oui ou aucune question ne peut être vérifiée rapidement. Ensuite, les réponses peuvent aussi être calculées rapidement?"
Je suis laissé se demander, comment la vitesse de vérification d'une réponse est-elle liée à la vitesse de génération d'une solution?
9 Réponses :
Il peut ou non être lié.
Les gens se soucient des problèmes de NP parce que nous voulons les résoudre rapidement et tout le temps, mais jusqu'à présent, nous n'avons pas trouvé de moyen de les résoudre rapidement. Nous voulons savoir s'il y a un moyen rapide de les résoudre ou si nous devrions abandonner essayer.
essentiellement, dans l'ensemble de NP, ou du temps polynomial non déterministe, des problèmes, la réponse peut être vérifiée en temps polynomial. La question est de savoir si tous ces problèmes peuvent être Si p = np est vrai, et de tels algorithmes sont découverts de nombreux problèmes qui sont difficiles à résoudre mais faciles à vérifier la solution, tels que des preuves, deviennent aussi faciles à résoudre quant à vérifier.
Wow très intéressant! Je peux voir pourquoi theres intérêt pour cela maintenant, TY!
Cette réponse ... n'est pas correcte. NP est l'ensemble des problèmes d'un vérificateur de temps polynomial. Ceci comprend tous les problèmes de P. Évidemment, si vous avez un solveur correct du temps polynomial, vous avez un vérificateur de temps polynomial. La question est de savoir s'il existe des problèmes dans NP qui ne sont pas aussi dans P.
@Borealid: J'ai corrigé ma réponse en fonction de ce que vous avez dit (je pensais à NP complète)
le "devenir aussi facile à résoudre quant à vérifier". était un aha! moment pour moi.
Supposons que je suis remis une solution à un problème "dur" par un magicien et je peux facilement vérifier si cette solution est correcte ou non. Mais puis-je calculer cette solution moi-même? (temps polynôme)
C'est exactement la question.
Supposons que vous ayez eu un énorme parallélisme - même si vous vouliez. Vous pouvez ensuite générer simultanément toutes les solutions possibles, vérifiez lequel de ceux-ci était correct et émis une solution correcte. En présence d'un parallélisme infini, il s'agit d'une méthode de génération d'une solution. L'ensemble des problèmes de NP est ceux pour lesquels cette procédure fonctionnerait rapidement, car la seule étape de calcul intéressante que celle-ci effectue vérifie si des solutions sont correctes, ce qui peut être effectué efficacement pour des problèmes dans NP. Notez que pour d'autres problèmes, même ce parallélisme ne nous permettrait pas de trouver des solutions rapidement, car elle nécessite que la vérification des solutions soit facile.
Mais nous n'avons pas de parallélisme infini. Pouvons-nous en quelque sorte le simuler, avec seulement une quantité polynomiale de frais généraux? Si tel est le cas, nous pourrions imaginer exécuter la procédure ci-dessus et trouver efficacement des solutions pour chaque problème pour lequel la vérification était facile. Ceci est la question P vs. NP.
Intuitivement, il semble clair que la réponse est "non" (c'est-à-dire P! = NP). Comment pourrions-nous éventuellement simuler un parallélisme infini? C'est ce que presque tous les experts croient. Mais c'est un mystère comment le prouver et une valeur de 1 000 000 $ en argent.
Ce problème a été résolu aujourd'hui!
(éventuellement.)
Peut-être. Je n'ai aucune connaissance en profondeur dans de multiples disciplines pour le vérifier moi-même, ni le désir de passer par une preuve de cent page. Je dis que nous laissons les experts en discuter pendant quelques années et voir ce qu'ils disent.
Malheureusement non. Bien que cela ait généré beaucoup d'intérêt médiatique, cette dernière tentative de preuve semble aussi défectueuse que les autres tentatives précédentes.
@David & Aaron: Ouais, tout est totalement sur ma tête. Par une certaine distance considérable.
Couverture supplémentaire (et plus de détails) ici: YEGISTER.CO.UK/2010/ 08/11 / the_p_versus_np_problem y compris un lien utile à une explication plus simple de ce que le problème est le suivant: Claymath. org / populaire_lectures / minesweeper
S'ils sont liés ou non est l'une des "problèmes de millénaire" de Claypool Foundation, et ils donneront un million de dollars à quelqu'un qui fournit une preuve appropriée qui tient compte de quelques années d'examen intense.
Les types de questions sont plus liés qu'aucune définition, car une autre définition d'un problème NP est une solution qui peut être résolue efficacement avec un ordinateur arbitrairement parallèle.
Une chose qui intéresse vraiment les gens est l'absence d'une preuve. Il y a des preuves pour des questions similaires, mais pas celle-ci. Cela intrigue des personnes, en particulier des mathématiciens, puisqu'une preuve susceptible d'apporter beaucoup d'informations sur d'autres choses. C'est apparemment le cas pour la preuve de Perelman de la conjecture de la POINCARE, un autre des problèmes du millénaire.
Un autre problème est l'impact que cela pourrait avoir. À l'heure actuelle, peu de gens croient qu'il existe une méthode efficace pour résoudre des problèmes de NP-complets, donc une découverte que p! = NP aurait peu d'impact pratique. Une découverte d'une manière efficace de résoudre les problèmes de NP-Complets révolutionnaliserait beaucoup d'informatique. Il faudrait beaucoup de choses beaucoup plus facilement et détruirait la cryptographie comme nous le connaissons en faisant de la script facile.
Perelman a prouvé la conjecture de la pratique et non l'hypothèse de Riemann.
@Aaron: Merci beaucoup. Éditer de manière appropriée.
C'est un fait de base de la complexité de calcul que SO Maintenant, la plupart des informaticiens croient que p est la classe de toutes les langues pouvant être calculée en temps polynomial par une machine à trouble déterministe. Un ordinateur moderne ressemble beaucoup à une machine à trouble déterministe, sauf qu'une machine de Turing a essentiellement une mémoire infinie. Cette distinction est généralement ignorée à des fins pratiques.
np est la classe de toutes les langues pouvant être calculée en polynôme de temps par un non -déterminaliste. Une machine à trouble non déterministe ne correspond à aucun dispositif mondial réel.
np est équivalent à la classe de langues dont les problèmes de vérification sont dans p . En fait, np est parfois défini comme cette classe; Les deux définitions sont interchangeables et la définition de vérification bénéficie d'une pertinence directe sur les ordinateurs déterministes-Turing-Machine dans le monde réel.
np est la classe de problèmes vérifiable en poly-time sur une machine "réelle" et solvable en poly-time sur une machine théorique très similaire. Ainsi, les questions de solvabilité et de vérifiabilité sont liées.
p et np sont pas équivalent; C'est-à-dire qu'il existe des langues calculables en poly-timide par une machine à trouble non déterministe mais non par une machine à trouble déterministe, ou de manière équivalente qui ne sont pas solvables en poly-tige par une machine à trouble déterministe, mais dont les solutions peuvent être vérifiées en poly-time par une machine de Turning déterministe.
Il n'y a pas de relation directe ici cependant. Il peut y avoir une sensation intuitive que la vérification d'une réponse est plus facile que de générer une réponse dans le cadre d'une génération serait de s'assurer que la réponse est correcte. Ainsi, on pourrait adopter une approche de force brutale pour essayer différentes solutions, mais cela a tendance à conduire à des complexités exponentielles qui sont au-delà de P, ou c'est ce que je me souviens de la complexité de classe il y a des années.
non, p = / np.
La réponse est co-np-asymétrique-partiellement-complète
Voir ma réponse complète ici sur mon site Web:
singularitarientechnologies.wordpress.com
Pour résumer essentiellement la réponse à votre question, la réponse est non, généralement, sauf dans une seule instance où p = np, ergo la réponse de Co-NP-asymétrique partiellement incomplète / complète.
Pour ce faire, j'ai utilisé google.com comme une base de données qui pourrait me donner une réponse vérifiée en temps polynomial, puis je voulais voir si la réponse serait calculable sur la meilleure réduction axiomatique du polynôme, composé de termes exponentiaticés. et intrinsèquement, la réponse est qu'avec plus de deux variables (exposants dans ce cas), la réponse n'est pas calculable, même si nous saurions quelle est la réponse vérifiée.
Évidemment, cela laisse des pirates de chapeau noir avec efficacement aucune alternative, comme dans les futures algorithmes de cryptage ne seront pas si simples. En outre, il s'agit techniquement d'une seule instance où p = np, car axiomatiquement, un polynôme doit être composé de plus d'un terme, ergo p = / = np variables iff> = 3 et p = npfables IFF <= 2.
Lire ma documentation complète sur mon site Web ou sur Google Drive, je fournis également un lien de tableur à mon travail sur singularitarientechnologies.wordpress.com
Qu'est-ce que cela signifie efficacement? À l'avenir, il n'y aura pas de piratage de chapeau noir, même si vous prenez en compte les tentatives de réduction axiomstiquement des attaques de cryptage via deux modulo deux, cela ne fonctionnera tout simplement pas avec le cryptage avancé (cryptage polynomial complexe, avec des mises en garde et des cloches et des sifflets pour le faire. beaucoup plus difficile d'essayer même de casser un chiffre ou de toute référence cryptée ..)
Tout le point de p =? NP est de répondre à votre question.
Bien comprendre cela ne résoudrait pas à résoudre P vs. NP? Il y a beaucoup d'informations déjà là-bas pour vous. Recherchez "Cycle hamiltonien". C'est un exemple qui est soumis à l'intuition.
En d'autres termes, "Ouais, mec, nous nous demandons tous la même chose."
Ok, puis laissez-moi reformuler: pourquoi pensent-ils qu'ils sont liés? Pourquoi devraient-ils être liés? Ils doivent avoir des raisons.
Je n'ai aucune idée. Si j'avais une idée, j'essaierais de le publier dans un journal et je ne serais pas disposé à vous dire de sorte que mon article touche la presse. Mais encore une fois, je n'ai aucune idée. Et j'ai déjà passé suffisamment de temps à me réfléchir à ce que je préférerais faire pression sur la pression dans ma maison que de travailler à ce sujet aujourd'hui.
@jason Vous posez des questions sur une question assez complexe dans la théorie des sciences informatiques, vous êtes probablement préférable de prendre une classe pour avoir une compréhension complète du sujet.
Est-ce une "vraie question?" J'ai voté près.
Oh, et dernier j'ai regardé le livre de Garey & Johnson Ordinateurs et Intractability a été considéré comme une bonne base pour étudier le sujet. Cela nécessite une connaissance de la théorie des automates et n'est pas uniformément facile.
@Heath: Je l'appellerais une vraie question. C'est responsable de manière raisonnablement objective.
Parce qu'un moyen possible de vérifier une solution donnée consiste à résoudre le problème à nouveau. S'il y a un moyen plus rapide de vérifier une solution, cela signifie-t-il qu'il existe également un moyen plus rapide de résoudre le problème aussi?
Considérant que cela semble être une vraie question, pourquoi est-ce la communauté wiki?
@David - non ce n'est pas le cas. La seule réponse est "c'est une question de recherche ouverte". La OP ne demande pas de définitions de P et NP, bien qu'il ait accepté une réponse à cette question. Lisez littéralement, trouvant une relation complexité de temps [vis. "Comment la vitesse de vérification d'une réponse est-elle liée" utilisée dans le texte OP] entre P et NP réglerait la question P vs. NP.
Non, l'OP demande pourquoi quiconque penserait que la vérification et la génération sont liées ...
Il me semble que la vérification sera toujours plus facile que la résolution. Lors de la vérification, vous avez donné une entrée (réponse) et vous venez de le brancher où X est. Résoudre les offres de manipulation d'une équation ou d'essayer de multiples variables. Ou regardez-le à partir d'un point de vue d'entropie: il est plus facile d'ajouter une complexité que de le sortir. (Exemple: secoue un pot de sable noir avec une couche de sable blanc .. Essayez maintenant de retirer le sable blanc.) Il semble que sa cible aussi énorme est le facteur "Et si ..." vraiment cool. Mais maintenant, il semble que ce soit comme prouver un négatif.
Quelqu'un a publié un papier à quelques jours, il y a quelques jours, prétendant avoir prouvé P! = NP. Je n'ai pas pu le télécharger à l'époque (j'imagine que le serveur était submergé) et j'ai depuis perdu le lien. Tout le monde en savait à ce sujet?
Probablement pas le même article, mais vous serez capable de google à partir des données de la part: allvoices.com/contribuked-news/...
@jason: Vous penseriez que la vérification serait plus facile que de résoudre. Maintenant, prouvez-le dans ce cas particulier. C'est le point critique. Puisque la plupart des gens croient que p! = NP (que la vérification est plus facile que la résolution, dans ce cas) et agir en conséquence, la preuve est ce qui est important.
@jason, ce n'était pas le même article, mais j'ai pu le trouver en googling le nom du gars. Des trucs intéressants ... je me demande où ça ira. Et je me demande si la réponse acceptée sur cette question devra être modifiée si elle est prouvée correcte :)