Discussion:Problème P = NP

Une page de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Autres discussions [liste]
  • Suppression
  • Neutralité
  • Droit d'auteur
  • Article de qualité
  • Bon article
  • Lumière sur
  • À faire
  • Archives


Proposition de démonstration[modifier le code]

Bonjour, il me semble que cette page est dédiée au discutions sur l'article. Je souhaite donc vous faire part de la démonstration suivante.

La démonstration :

- Soit un problème NP dont la solution n'admette que deux possibilités (Vrai ou Faux)

- Une fois la solution connue, la vérification est forcément NP, sinon le problème aurait été P (pour trouver la solution, il aurait suffit de vérifier les deux solutions possibles en problème P et donc le problème n'aurait pas été NP....)

J'apprécierais, bien volontier, vos commentaires, fussent-ils négatifs.

Ce n'est absolument pas le lieux pour ce genre de question, mais je vais y répondre un Peu (et pas plus que ça) : il y a confusion entre solution et solution. Un problème de décision c'est un problème dont la solution est soit vraie soit faux. C'est le cas de problème SAT. Cependant SAT possède un nombre exponentiel d'affectation aux variables possibles. Les affectations qui satisfont la formules sont aussi appelées "solution", et c'est une telle affectation qu'on recherche en général pour répondre "oui" à la question (répondre "non" revient à démontrer qu'il n'y en a pas. Bref en général la difficulté se trouve dans la recherche de solutions (affectations). Pour SAT, vérifier qu'une affectation est ou n'est pas solution est très facile. Donc non, dans le cas général, il n'y a pas "que" deux solutions possibles, sinon bien évidemment le problème aurait déja été résolu :) TomT0m (d) 31 janvier 2011 à 22:19 (CET)
Que nous importe le cas général ???? on cherche une solution particulière pour infirmer le problème !!!! Ok, ma solution n'est pas générique, mais elle remet en cause tout l'édifice, c'est la seule chose qui compte ou alors il faut redéfinir le problème ....
 vous, je ne sais pas, mais à nous, le cas général importe assez, vu que c'est lui qui constitue le problème. Pour gagner un million de dollars, le plus souvent, on a intérêt à bien lire l'énoncé...--Dfeldmann (d) 1 février 2011 à 07:13 (CET)
Juste je pense qu'il pourrait être intéressant de lire les définitions formelles des machines de Turing déterministe et non-déterministes, avant de venir poster des démonstrations Clin d'œil. --Pparent (d) 27 mars 2011 à 15:43 (CEST)

Accessibilité[modifier le code]

Bonjour, je ne suis pas certain que l'article dans son état actuel (et c'est le cas de nombreux articles ayant trait a la théorie de la complexité) soit accessible par un lecteur non averti. Je serais d'avis de mettre un paragraphe de vulgarisation avec des exemples concrets, si possible, qu'en pensez-vous ? Argos42 (d) 16 août 2010 à 13:46 (CEST)

Tu sais, il est aussi possible de présenter le problème comme cela, ou comme cela, et donc j'avais déjà l'impression de vulgariser au maximum ! Mais tout est relatif Sourire. Mais comme je connais le sujet, je suis très mal placé pour savoir ce que ressent ou comprend un néophyte, et ta remarque est sans aucun doute valable. N'hésite pas ! Le premier paragraphe "Complexité des algorithmes, classes P et NP" est là pour rappeler les bases justement et je pensais mettre des exemples concrets d'algos P ou NP dedans. C'est peut-être cela qui manque. Cordialement --Jean-Christophe BENOIST (d) 16 août 2010 à 13:59 (CEST)
Désolé j'ai pas eu trop le temps de me pencher là dessus, mais ta nouvelle intro me semble beaucoup plus accessible. (Je suis informaticien aussi, donc faudrait voir avec un extérieur. Argos42 (d) 17 août 2010 à 22:10 (CEST)

Il serait quand même peut-être bien de faire référence aux machines de Turing, c'est important pour la compréhenssion de la définition formelle du probléme, et on peut voir avec le sujet de discussion au dessus que le problème P=NP peut être mal compris à cause de cela.--Pparent (d) 27 mars 2011 à 16:17 (CEST)

la question est de savoir si un signal électrique peut répondre à la question aussi vite que si elle étais déjà dans la question? je ne comprend pas la rationalité du problème, peut on déjà comparer P=NP pour quelque forme de compléxité que ce soit?
http://fr.wikipedia.org/wiki/Loi_en_carr%C3%A9_inverse
Il s'agit ici de complexité algorithmique, et pas d'autre chose. La complexité algorithmique se définit pour des machines qui soient équivalentes - du point de vue du calcul - à des machine de Turing, c'est à dire la plupart des machines concrêtes qu'on connait (si on néglige la mémoire finie). On compte deux choses pour la complexité algorithmique : le nombre d'étape du calcul et la quantité de mémoire utilisée pour le calcul. Pour la transmission d'information, on considère que la taille de la machine est bornée, c'est à dire qu'on a pas trop à se préoccuper du temps de transmission de l'information, un transfert c'est typiquement une étape du calcul et rien d'autre.
La question n'est pas de savoir un signal est contenu dans un autre, mais effectivement c'est sans doute pas très clair si on ne connait pas les notion abordées. Peut être qu'un exemple aiderait à clarifier les notion de résolution et de vérification: par exemple le problème des mariages stable : on dispose d'un ensemble d'homme et d'un ensemble de femme. Chaque homme a classé par ordre de préférence les femmes comme partenaire en vu d'un mariage, les femmes ont fait de même. On doit former des couples homme femmes.
Bien entendu, on ne forme pas les couples au hasard, il par exemple serait facheux qu'alice et bob soient mis en couple alors qu'alice aurait préféré charles et que danielle aurait préférée bob si charles et danielle sont aussi mis en couple.
Vérifier une solution, ce serait étant donné un ensemble de couple déja formé décider si elle est ou pas stable.
trouver une solution, ce serait trouver un ensemble de couple stable.
Pour certaines variantes de ce problème, la vérification est dans la classe de complexité P et trouver une solution est dans la classe NP. Pour la variante de base, il existe une méthode de résolution efficace qui place aussi bien la vérification que la recherche de solution dans la classe P, cf. en:Stable_marriage_problem
TomT0m (d) 25 juin 2012 à 19:35 (CEST)
L'exemple que tu donnes peut être stable si Bob préfère Alice et que Charles préfère Danielle. Il y a instabilité si deux personnes se préfèrent l'un l'autre à leur partenaire. Ambigraphe, le 26 juin 2012 à 21:56 (CEST)
Oui c'est exact, je devais pas avoir les yeux en face des trous /o\ TomT0m (d) 26 juin 2012 à 22:16 (CEST)

Quantique[modifier le code]

Bonjour, question sur la machine quantique. N'est il pas possible de concevoir une machine de Turing non déterministe en informatique quantique ? Car si c'est la cas, cela implique que l'on peut résoudre en temps polynomial les problèmes NP, car d'après Théorie de la complexité des algorithmes : La classe NP des problèmes Non-déterministes Polynomiaux réunit les problèmes de décision qui peuvent être décidés sur une machine non déterministe en temps polynomial. Argos42 (d) 19 août 2010 à 11:49 (CEST)

Très bonne question. Je n'ai pas encore vu de source qui traite explicitement et directement cette question (peut-être parce que la réponse est considérée - par les spécialistes du domaine ! - comme évidente), donc je vais te donner mon avis personnel. Une machine non-déterministe est une notion purement théorique (et archaïque car la classe NP a été définie comme cela au départ, mais on peut la définir autrement et plus simplement aujourd'hui). Elle est théorique car elle correspond une capacité qui "n'existe pas" (un peu comme les Oracles, qui sont aussi utilisé en théorie de la complexité), même en quantique : la capacité de choisir parmi N chemins, simultanément, ceux qui vont accepter en définitive le langage ou non. Il faut donc une capacité de "prédiction", "d'intuition" qui n'existe pas à moins de penser que la rétro-causalité existe (ce qui n'est d'ailleurs pas tout à fait exclu en MQ, mais très peu probable et très "politiquement incorrect"). Un algorithme quantique va choisir entre N chemins simultanément, mais purement au hasard, sans savoir si le chemin mène à une acceptation ou non. Il faudrait en dire un mot dans cet l'article (ou dans l'article - qui n'existe pas non plus - sur la classe NP), mais tant que je n'ai pas trouvé de source explicite, j'hésite à écrire des choses à ce sujet. Cordialement --Jean-Christophe BENOIST (d) 19 août 2010 à 13:27 (CEST)

Lien cassé "complexité NP"[modifier le code]

Dans la première phrase La relation entre la classe des algorithmes de complexité P et la classe des algorithmes de complexité NP est un problème non résolu... le lien complexité NP semble cassé (mais c'est curieux qu'il apparaisse en bleu, il ne devrait pas apparaître en rouge ? ). Je suppose que ça devrait aller vers le paragraphe Théorie de la complexité des algorithmes#Classe NP et classe Co-NP (complémentaire de NP), mais je suis pas vraiment un spécialiste... j'ai déjà du mal avec les P simples (et / ou les complémentaires tangentielles de P ça va de soi/non soi NP) Touam (d) 20 août 2010 à 14:17 (CEST)

En effet, le titre a dû changer récemment. Merci pour la remarque ! Mais de toutes manières il manque aussi un article sur ce sujet, et l'idéal serait de pointer directement sur l'article. J'essaierais de faire un stub dès que j'en aurais fini avec cet article, si personne ne s'est dévoué entre temps (appel du pied à la cantonnade Clin d'œil ) Cordialement --Jean-Christophe BENOIST (d) 20 août 2010 à 14:27 (CEST)

Cryptographie à clé publique[modifier le code]

Explication de ma modification : aucun algorithme de chiffrement à clé publique ne repose sur un problème prouvé NP-complet ou même supposé NP-complet. Par exemple, la factorisation (plus exactement, le problème de décision associé) est dans donc pas NP-complet à moins que la hiérarchie polynomiale ne s'effondre à l'ordre 1. Nordald (d) 27 mars 2011 à 15:33 (CEST)

Peux tu rappeler pourquoi un probléme qui est dans ne peut pas être NP-complet si P différent de NP? merci --Pparent (d) 27 mars 2011 à 18:58 (CEST)
Ce n'est pas tout à fait ça que je veux dire. Si P = NP, alors on a NP = CoNP.
Dans l'autre sens, non. On pourrait avoir P ≠ NP et NP = CoNP (donc tous les problèmes NP-complets seraient dans CoNP). Mais ça signifierait que la hiérarchie polynomiale s'effondre à l'ordre 1, ce qui est généralement considéré comme improbable. En tout cas, c'est ce qui est dit dans les articles anglais Polynomial hierarchy ("it is an open question whether any of these inclusions are proper, though it is widely believed that they all are") et Integer factorization ("If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, and therefore integer factorization is widely suspected to be outside both of those classes.").
Ainsi, le cas le plus vraisemblable est P ≠ NP et NP ≠ CoNP, qui implique qu'aucun problème NP-complet ne peut être dans CoNP (par réduction, cela entraînerait et donc vue la définition de ces classes). Nordald (d) 27 mars 2011 à 22:00 (CEST)
Oui donc en fait c'est plutot: un probléme NP qui est dans CoNP ne peut pas être NP-complet si NP différent de co-NP, ce qui semble à premiére vue se démontrer facilement.--Pparent (d) 27 mars 2011 à 22:43 (CEST)
C'est bien ça. --Nordald (d) 30 mars 2011 à 21:18 (CEST)
Du coup est-ce que cette phrase:"Parmi ces problèmes NP-Complets se trouve également la cryptanalyse des systèmes de cryptographie à clé publique" n'est pas fausse ou en tous les cas non-démontré.--Pparent (d) 30 mars 2011 à 23:01 (CEST)
C'est non démontré et improbable, selon l'explication ci-dessus. En fait, P ≠ NP est une condition nécessaire à la sécurité des transactions bancaires, mais pas suffisante. Donc ce serait peut-être mieux d'enlever les références à la cryptographie, sauf à un endroit où on explique cela ? Nordald (d) 1 avril 2011 à 14:20 (CEST)
J'ai reformulé un des passages, par contre j'aurai un peu plus de mal pour "La cryptographie à clé publique et la sécurité bancaire serait assurée, mais plus encore..." car je n'ai qu'une vague idée de ce qui est expliqué après le "plus encore". Mais à mon avis, la formule qu'il y a juste après ("apporterait des pistes pour [...] démontrer plus formellement la sécurité des systèmes cryptographiques") est plus correcte et suffisante. --Nordald (d) 1 avril 2011 à 21:43 (CEST)
Il faut aller voir dans la source, c'est le texte qui commence par « We can do much more than just public-key cryptography using hard problems [...] ». Le "plus encore" est dans l'idée du "much more". Il y a des allusions à cette propriété également dans d'autres sources si mes souvenirs sont bons. Cordialement --Jean-Christophe BENOIST (d) 1 avril 2011 à 22:05 (CEST)
Le paragraphe 7 de [1] s'intitule "Using Hardness" et d'après ce que je comprends, il est consacré non pas aux conséquences de P != NP, mais à l'intérêt que peuvent représenter les problèmes difficiles à résoudre (qui existent si P != NP, mais ça ne veut pas dire que démontrer P != NP fournit automatiquement des problèmes utilisables pour les applications mentionnées).
L'auteur indique que les problèmes difficiles peuvent être utilisés pour la cryptographie (mais précise clairement que P != NP ne suffira pas à garantir la sécurité de ces sytèmes - phrase précédente de celle que vous citez) et pour "beaucoup plus", c'est-à-dire ces preuve à divulgation nulle de connaissance. Mais je ne vois pas dans la source le fait que P != NP impliquerait l'existence de telles preuves pour tout problème de NP mais non P (d'ailleurs qu'est-ce que signifie cette parenthèse "et non P" ? dans [2], section 4.3, p. 18, je vois plutôt l'inverse : "Cleary, every set in P (or rather in BPP) has a 'trivial' zero-knowledge proof (in which the verifier determines membership by itself)")
Le théorème 4.2 p. 19 de ce même document [3] indique "s'il existe des fonctions à sens unique, alors tout langage S de NP a une zero-knowledge interactive proof" et pas "si P != NP, alors tout langage S de NP a une zero-knowledge interactive proof".
Bon, je suis en train de discuter sur des points que je ne comprends pas totalement, je n'ai pas tout lu en détail et je doute d'avoir plus de temps à y consacrer dans l'immédiat. Je ne veux pas vous obliger à vous lancer dans des explications détaillées à cause de ça donc si vous préférez, on peut en rester là, mais il me semble qu'il reste des points à éclaircir dans ce paragraphe. --Nordald (d) 2 avril 2011 à 00:39 (CEST)
Toute remarque et demande de clarification ne peut aller que dans le bon sens. Le paragraphe (qui est tout de même dans un papier consacré entièrement à P=NP) explore à mon sens les conséquences de P!=NP, comme en témoigne la phrase d'introduction du paragraphe "But we expect P != NP to hold in very strong ways. We can use strong hardness assumptions as a positive tool, particularly to create cryptographic protocols". Quand tu dis "s'il existe des fonctions à sens unique, alors tout langage S de NP a une zero-knowledge interactive proof" et pas "si P != NP, alors tout langage S de NP a une zero-knowledge interactive proof", c'est vrai, mais personne ne prétends que c'est l'existence de ces preuves qui est impliquée par P!=NP, mais en revanche c'est l'utilisabilité de manière sécure de ces preuves qui est impliquée. Et c'est très important. Je crois avoir d'autres sources qui parlent de ce même sujet, dans le contexte P=NP, il faut que le les retrouve. Cordialement --Jean-Christophe BENOIST (d) 4 avril 2011 à 15:46 (CEST)

classe de complexité = classe de problème, pas classe d'algorithme ?[modifier le code]

« En mathématiques, et plus précisément en informatique théorique, la relation entre la classe des algorithmes de complexité P et la classe des algorithmes de complexité NP est un problème non résolu »

Il me semble bien que P et NP ne sont pas des classes d'algorithme, mais des classes de problèmes ... un problème est dans P si il existe un algorithme polynomial permettant de résoudre chacune de ses instances, et dans NP si il existe un algorithme non déterministe polynomial. Je me trompe ou c'est un abus de langage ? TomT0m (d) 28 mars 2011 à 12:19 (CEST)

Non tu as raison! Il faudrait revoir cette partie --Pparent (d) 28 mars 2011 à 13:03 (CEST)
N'hésitez pas ! J'ai essayé de faire du mieux que je pouvais avec cet article, en ayant demandé de l'aide, mais je me suis retrouvé tout seul pour le faire. Je suis content de voir de d'autres le prennent en main maintenant, avec toute la compétence et la rigueur que cet article mérite. Cordialement --Jean-Christophe BENOIST (d) 28 mars 2011 à 13:27 (CEST)


Sur le fond, j'avais en tête le fait que l'on parle de la théorie de la complexité des algorithmes, et non pas théorie de la complexité des problèmes. La dénomination "théorie de la complexité des algorithmes" est utilisée notamment par Jean-Paul Delahaye. Je pense qu'en effet il est plus rigoureux de parler de la complexité des problèmes. Cela pose plus globalement le problème de la structuration des articles sur ce sujet sur WP, sur laquelle il y a eu débat jadis. Au départ, il y avait deux articles (largement redondants, ce qui posait problème) sur le sujet : un article plus orienté "complexité des algorithmes" (avec notation grand O etc..), et un article plus sur la complexité des problèmes (P, NP etc..). Mais la distinction n'était pas claire, et on aboutissait à deux articles très redondants. Il y a eu fusion de ces deux articles dans théorie de la complexité des algorithmes. Il serait peut-être judicieux de reparler de ce problème et de cette structuration. Globalement, il y a un grand chantier potentiel sur tous ces sujets : il manque beaucoup d'articles (pas d'article individuels sur chaque classe de complexité par exemple), et cet article est tout neuf alors qu'il s'agit d'un des article les plus importants du domaine. Encore une fois, content de voir du sang neuf dans ce domaine. Cordialement --Jean-Christophe BENOIST (d) 28 mars 2011 à 13:53 (CEST)

Faitfait, J'ai changé algorithme par problèmes. P et NP sont bien des classes de problèmes et le problème P=NP n'a de sens que si on parle de problèmes et non d'algorithme. (Il est toujours possible de trouver des algorithme d'une complexité démente pour résoudre des problèmes en fait dans P). Ou plutot la question est "existe t'il un algorithme polynomial pour résoudre les problémes NP ?"--Pparent (d) 28 mars 2011 à 15:20 (CEST)

« et qu'il n'existe pas d'algorithme meilleur que la force brute pour les traiter. » J'ai aussi un gros doute sur cette affirmation tout d'un coup, un algorithme peut être meilleur que la force brute en étant quand même exponentiel dans le pire des cas ... en fait on fait déja des algorithmes bien meilleurs que la force brute en moyenne, même si ils restent exponentiels. J'ai pas viré l'affirmation tout de suite parce que j'ai un doute sur le fait que ces algorithmes ne puissent pas être meilleurs que la force brute pour certaines instances de problème, mais ça mériterait au moins d'être étayé. TomT0m (d) 28 mars 2011 à 23:17 (CEST)

Si P!=NP alors il n'existe pas d'algorithme meilleur en complexité maximale que la force brute, après cela ne veut pas dire qu'en moyenne il n'en existe pas de meilleur(mais on ne peut pas dire qu'ils soient foncièrement meilleurs).Mais cette affirmation pourrait gagner à être reformulée. --Pparent (d) 28 mars 2011 à 23:25 (CEST)
La phrase pose à mon avis trois problèmes :
  1. Il en existe des problèmes hors d'atteinte, il suffit de chercher en dehors de NP (j'avais mis un paragraphe ).
  2. Il peut exister des solutions plus efficaces que la force brute pour un problème NP-complet (l'exemple-type est le problème du voyageur de commerce, qu'on peut résoudre en par programmation dynamique, ce qui est mieux que l'algorithme naïf en n!).
  3. La NP-complétude dit quelque chose sur les pire cas, certains problèmes NP-complets peuvent résolus en temps polynomial en moyenne (en mettant loi de probabilité naturelle sur les entrées).
Mais c'est difficile d'être précis en restant simple. Je suggère de passer rapidement sur le (1) en disant simplement "une large classe de problèmes", d'enlever la fin de la phrase selon le (2) et d'ignorer le (3) vu que ça me semble moins essentiel, ce qui donnerait :
« S'il est avéré que P n'est pas égal à NP, cela signifierait qu'une large classe de problèmes sont définitivement et fondamentalement hors d'atteinte du calcul dans un temps raisonnable. »
Ça vous convient ? --Nordald (d) 30 mars 2011 à 21:18 (CEST)
Ca me parait bien Clin d'œil --Pparent (d) 30 mars 2011 à 21:40 (CEST)
Bonnes remarques, mais cette version me semble trop imprécise du coup. On perd l'idée que on reste dans une complexité équivalente à la force brute. Pourquoi pas :
S'il est avéré que P n'est pas égal à NP, cela signifierait qu'une large classe de problèmes sont définitivement et fondamentalement hors d'atteinte du calcul dans un temps raisonnable, et qu'il n'existe pas d'algorithme fondamentalement meilleur que la force brute pour les traiter.
? Ou quelque-chose dans l'idée que on reste comparable à la force brute à la fin. Cordialement --Jean-Christophe BENOIST (d) 30 mars 2011 à 21:41 (CEST)
C'est l'idée même de comparaison avec la force brute qui me pose un problème. Quel est le sens de "fondamentalement meilleur" ? Passer de "recherche exhaustive" à "programmation dynamique" pour le voyageur de commerce fait gagner n! / 2^n, nettement supérieur à ce qu'on gagnerait en passant de "programmation dynamique" à "polynomial". Et si P != NP, je ne crois pas que ça empêche de résoudre un problème NP-complet en temps sous-exponentiel (par exemple ). --Nordald (d) 30 mars 2011 à 22:38 (CEST)
Ah ! Ta dernière phrase est intéressante : je n'avais pas cela en tête. Tu es sûr qu'il serait théoriquement possible de résoudre un problème NP-Complet en temps sous-exponentiel avec P<>NP ? Cela a été démontré ? Je suis très intéressé par une source. Si oui, alors je suis d'accord avec toi. Cela dit, je comprends ce que tu veux dire. Quand j'ai rédigé Algorithme de Grover, je pense que je n'aurais pas été d'accord si quelqu'un avait dit que ce n'est pas une amélioration substantielle de la recherche par force brute pour les problèmes NP-Complets, et pourtant on reste en complexité exponentielle ! La tournure de phrase n'est pas facile à trouver, et - en l'absence de source pour bien la formuler - autant effectivement s'abstenir. Je suis donc d'accord avec ta proposition. Cordialement --Jean-Christophe BENOIST (d) 30 mars 2011 à 23:30 (CEST)
La question me parrait plutot est-ce qu'il a été demontré que l'on ne pourrait pas le résoudre en temps sous-exponentiel. En effet si on ne sait déja pas si on peu les résoudre en temps polynomial je vois mal comment on peut affirmer qu'il ne peuvent être résolut en temps sous-exponentiel. La seule solution pour que ce soit impossible par le seul fait que P!=NP serait que l'on est démontré que tous les problémes se résolvant en un temps sous-exponentiel peuvent se résoudre en un temps polynomial.--Pparent (d) 31 mars 2011 à 07:30 (CEST)
En tout cas, ce point est important et intéressant et mériterait d'être développé dans l'article. Je vais essayer de trouver des sources qui traitent et éclaircissent ce point. Cordialement --Jean-Christophe BENOIST (d) 31 mars 2011 à 10:29 (CEST)
Je pense qu'une bonne partie de nos interrogations est traité par en:Exponential time hypothesis. Donc, en effet, rien n'est démontré, ni dans un sens ni dans l'autre, mais il existe tout de même une hypothèse forte. Il faudra penser à faire notre interwiki sur cet article ;) Cordialement --Jean-Christophe BENOIST (d) 31 mars 2011 à 20:36 (CEST)
J'allais dire que je n'avais pas trouvé grand chose, à part J.-P. Delahaye qui affirme dans Complexités que « On ne sait pas si ce problème de la 3-colorabilité est dans la classe P, car les seuls algorithmes systématiques connus sont du type décrit au-dessus qui procèdent par énumération et demandent un temps de travail exponentiel » (p. 94). J'ai cherché dans des livres de complexité, mais vu les références de l'article en:Exponential time hypothesis, c'est au-dessus du niveau de ceux que je connais. Nordald (d) 31 mars 2011 à 20:50 (CEST)

C'est peut-être un peu capilo-tracté, mais je suis même pas sur que l'on puisse dire que si P!=NP alors "cela signifierait qu'une large classe de problèmes sont définitivement et fondamentalement hors d'atteinte du calcul dans un temps raisonnable.". Imaginons que l'on puisse résoudre un probléme NP-complet en avec l'inverse de la Fonction d'Ackermann, ce ne serait pas polynomial mais ce serait en un temps trés raisonnable. Mais bon je pense que l'on peut quand même laisser la phrase comme ça, je chipote un peu Clin d'œil. --Pparent (d) 3 avril 2011 à 23:40 (CEST)

Oui, un peu Clin d'œil Je pense qu'il est communément admis que P!=NP <=> temps de calcul non raisonnable pour les algorithmes NP-Complets. Si je reprends simplement les termes de Jean-Paul Delahaye, dans "Complexités" par exemple, "si vous démontrez qu'un seul problème NP-complet ne peut être résolu efficacement, alors vous aurez démontré [...] que P!=NP" ou bien "La résolution [du problème P=NP] pourrait surgir d'un algorithme résolvant efficacement un problème NP-Complet". Je pense que dans l'article, il faut rester à un niveau de vulgarisation similaire à celui de JPD. A la limite, si cette phrase pose vraiment problème, on peut reprendre exactement les mêmes termes : "cela signifierait qu'une large classe de problèmes ne peuvent définitivement et fondamentalement être résolus de manière efficace." Cordialement --Jean-Christophe BENOIST (d) 4 avril 2011 à 15:29 (CEST)

Présentation formelle du problème.[modifier le code]

Bonjour, j'ai écrit une première ébauche de présentation formelle du problème. N'hésitez pas à l'améliorer et à me dire ce que vous en pensez. --Pparent (d) 31 mars 2011 à 16:08 (CEST)

J'ai déjà put détecter pas mal d’erreurs que j'avais faites. Je pense que la section gagnerai beaucoup à être relue voir réédité. A noter que je me suis en partie inspiré de la définition officielle du problème. --Pparent (d) 31 mars 2011 à 16:48 (CEST)

Traitement en pratique des problèmes NP-Complets[modifier le code]

J'ai initié un paragraphe sur ce sujet, qui devrait répondre et préciser les préoccupations soulevées dans les discussions précédentes. Je compte me fonder essentiellement sur Exact algorithms for NP-hard problems: A survey. N'hésitez pas à contribuer ! Cordialement --Jean-Christophe BENOIST (d) 4 avril 2011 à 16:56 (CEST)

Algorithme sous-exponentiel et décomposition en facteurs premiers.[modifier le code]

Salut, Est-ce que tu as une référence qui montre que la décomposition d'un entier en facteurs premiers admet un algorihtme sous-exponentiel? (Il faut aussi remarquer qu'il est possible que la décomposition en facteurs premiers soit NP-complet).

merci Clin d'œil. --Pparent (discuter) 10 Avril 2011

J'ai sorti cela de en:Time_complexity#Sub-exponential_time : An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the general number field sieve, which runs in time about . Cette information est reprise sur en:General number field sieve. Ce n'est pas sourcé, mais cela me parait cohérent étant donné la complexité en . Cordialement --Jean-Christophe BENOIST (d) 10 avril 2011 à 23:14 (CEST)
A mon tour de te demander une source pour "il est possible que la décomposition en facteurs premiers soit NP-complet", étant donné que l'article en:Integer_factorization#Difficulty_and_complexity stipule que It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete. Clin d'œil --Jean-Christophe BENOIST (d) 11 avril 2011 à 00:34 (CEST)
Je n'ai pas de sources pour ce problème en particulier, mais a minima dans le cas ou P=NP alors la décomposition en facteur premier serait NP-Complet comme tout autre problème de P.--Pparent (discuter) 19 octobre 2015 à 02:26 (CEST)

Démonstrations non constructives d'existence d'algorithmes polynomiaux[modifier le code]

J'ai l'impression que l'explication de pourquoi le théorème ne prouve pas P=NP,pourrait être éclaircie un petit peu. En fait dans beaucoup des problèmes de décision NP-complet, comme le problème du sac à dos, le k fait nécessairement parti des entrés du problème. Donc si la complexité évolue exponentiellement ou même en théorie linéairement (puisque le codage se fait en log) par rapport à la valeur de k , alors l'algorithme ne peut être considéré comme polynomial du tout.

Cependant je crois que le problème du sac à dos (et d'autre problèmes), ou l'on coderai intentionnellement mal k afin que son codage ai une longueur linéaire par rapport à sa valeur serait quand même NP-complet (à confirmer). On peut même imaginer que certain problèmes de décisions qui seraient NP-complet, même pour k fixé, donc k ne faisant pas parti du tout de l'entrée.

On en arrive à des subtilités de codage des entrée pour bien cerner, le problème. Içi il n'est pas bien précisé quel problème propose de résoudre le théorème...

ps: Excusez moi, ça a bien évolué depuis la dernière fois que j'ai lu. Ça parait clair maintenant. --Pparent (d) 22 novembre 2011 à 21:12 (CET)

Je m'étais fait les mêmes remarques que toi, et c'est pourquoi j'ai modifié. Merci pour cette remarque tout de même ! Cordialement. --Jean-Christophe BENOIST (d) 22 novembre 2011 à 21:25 (CET)
En fait, j'ai à peu près recopié ce paragraphe de l'article Théorème de Robertson-Seymour ; quelqu'un pourrait-il jeter un oei sur l'original et vérifier que c'est correctement expliqué là-bas, ou corriger (et, au passage, peut-être même voter pour l'AdQ) ?--Dfeldmann (d) 23 novembre 2011 à 03:34 (CET)
A mon avis, il faut reporter les modifications dans Théorème de Robertson-Seymour, car la formulation actuelle dans cet article peut porter à confusion et interrogation. Je le ferais à l'occasion. Cordialement --Jean-Christophe BENOIST (d) 23 novembre 2011 à 11:20 (CET)

Introduction à revoir[modifier le code]

Je penses qu'il faut revoir l'introduction. D'abord il faudrait un ou deux paragraphes très informel présentant le problème de façon simple et accessible à tous même si l'on est pas familier avec les notions.

D'abords des trucs très généraux, dire que c'est un des problème actuel les plus important des mathématiques, qu'il y a un million mis en jeu par institut clay ect... Un peu comme c'est fait mais sans parler directement des classe de complexité.

Ensuite un paragraphe qui décrit le problème de façon très informel du genre "Pouvoir vérifier une solution rapidement, implique t'il de pouvoir la trouver rapidement?", et 1 ou 2 autres énoncés classiques du genre.

Ensuite je pense qu'il faut absolument se débarrasser "Les algorithmes de classe P sont les algorithmes dont le temps de traitement peut être majoré par un polynôme, en fonction du nombre N d'éléments à traiter (par exemple T(N) = N2). Les algorithmes de classe NP sont des algorithmes dont la vérification du résultat, une fois celui-ci connu, demande un temps polynomial." Car les algorithmes ne peuvent pas être de classe P ni NP, ce sont des classes de problèmes. Donc dans ce paragraphe on peut se permettre d'être plus précis et pointu donc éventuellement un peu moins accessible, grâces aux paragraphes précédent.

Je m'y mets dés que j'ai le temps, n'hésitez pas à m'aider, ou à me dire ce que vous en pensez Clin d'œil . --Pparent (d) 28 novembre 2011 à 20:58 (CET)

N'hésite pas ! --Jean-Christophe BENOIST (d) 28 novembre 2011 à 23:34 (CET)
Bonnes modifications de l'introduction, AMA. Merci pour cette amélioration de l'article ! Cordialement --Jean-Christophe BENOIST (d) 30 novembre 2011 à 16:11 (CET)

section "Complexité des algorithmes, classes P et NP"[modifier le code]

J'ai commencé un brouillon pour donner une idée de ce qu'est la complexité des algorithme, et introduire des intuitions sur P=NP pour les pas spécialistes, avec un maximum d'exemples et en essayant d'éviter les formalismes abscons.

Je sais pas si ça va finir dans l'article, ça risque de bouger / d'être résumé. N'hésitez pas à faire des commentaires, à me dire si c'est intéressant, si vous pensez que ça aurait sa place dans l'article, dans un article séparé, voir à faire quelques modifs.

c'est là : Utilisateur:TomT0m/intro_à_la_Complexité_et_à_P=NP

Je repasserai par ici quand j'aurai une version complétée. TomT0m (d) 1 décembre 2011 à 00:44 (CET)

Deux remarques :
  1. Les éléments de vulgarisation devraient plutôt être ventilés dans les articles respectifs, et d'ailleurs, il manque (cruellement) des articles individuels sur les classes P, NP, etc.. Pour le moment, tout est dans l'article théorie de la complexité des algorithmes. Pour moi, c'est ultra-prioritaire à la vulgarisation de ces classes, dans d'autres articles qui plus est. Si on met toute cette vulgarisation dans un seul article, cet article, ou dans théorie de la complexité des algorithmes, cela va faire trop Wikibooks et pas assez "encyclopédique", et noyer le sujet principal de l'article.
  2. La vulgarisation utilisée devrait se fonder sur une vulgarisation déjà publiée, autrement dit être sourcée. Les exemples, l'approche utilisée pour vulgariser est extrêmement subjective, beaucoup plus que l'approche académique qui est assez normalisée, surtout en sciences. Certaines approximations, inévitables dans une vulgarisation, apparaitront acceptables pour certains, inacceptables à d'autres. La pertinence des exemples idem. Il vaut vraiment mieux se fonder sur une approche déjà publiée pour éviter les opinions subjectives sur la pertinence de la vulgarisation.
Globalement, je pense qu'il faut éviter de prendre la moitié de l'article à vulgariser (d'où ventilation nécessaire). On peut être clair et didactique tout en restant concis; c'est plus facile à dire qu'à faire c'est vrai, mais la modification récente de PParent, qui va dans ce sens, montre que cela est possible. Cordialement --Jean-Christophe BENOIST (d) 1 décembre 2011 à 18:26 (CET)

Travelling Salesman (film 2012).[modifier le code]

Il faudra peut-être ajouter une référence au film Travelling Salesman qui va bientôt sortir et qui traite du problème P=NP. Mais je sais pas trop ou mettre ça. --Pparent (d) 12 juin 2012 à 19:15 (CEST)

En fait on pourrait peut-être faire une section références dans la culture populaire, car il y a aussi un épisode des simpsons qui fait référence au problème, ainsi qu'un épisode de numb3rs. --Pparent (d) 12 juin 2012 à 20:48 (CEST)

Je ne suis pas fan, à titre personnel, des sections "dans la culture populaire", qui s'avère être dans un grand nombre de cas un aspirateur à tout et n'importe quoi (ce qui n'est pas le cas de tes exemples, je pense !). Je ne m'opposerais pas à sa création, mais il faudrait une politique pour filtrer ce qui peut apparaitre dans cette section (si on en parle pendant 2 secondes dans un épisode d'une série par exemple, ce n'est pas pertinent AMA). Je proposerais des critères comme ceux que j'ai tenté de mettre en place sur Trou noir, dans lequel cette section était devenue catastrophique.
Si on édite Trou_noir#Culture_populaire (c'est en commentaire, on le le voit pas si on n'édite pas, nous avons :
Pour ne citer que les œuvres les plus pertinentes (les trou noirs étant très présent en culture populaire, on pourrait citer ici des centaines d’œuvres) les critères suivants devraient être pris en compte :
  • l’œuvre a pour sujet principal, ou comme « personnage principal » un trou noir/trou de vers.
  • le trou noir est secondaire dans l’œuvre, mais celle-ci nous apprend quelque chose d’encyclopédique sur les trous noirs.
  • l’œuvre doit posséder un article dans Wikipédia, ou être potentiellement admissible en tant qu’article.
En remplaçant "trou noir" par "problème P=NP", on a des critères qui peuvent tenir la route. "Travelling Salesman" semble, d'après ce que tu en dis avoir comme un des sujet principal le problème, donc c'est OK selon ces critères. Pour le reste, je ne sais pas. Cordialement --Jean-Christophe BENOIST (d) 12 juin 2012 à 22:53 (CEST)
Oui P=NP est même le sujet principal du film apparemment. Par contre pour les autres choses que j'ai cité ce n'est juste que des rapides références. Donc je propose d'attendre un peu que le film sorte peut-être.--Pparent (d) 13 juin 2012 à 09:22 (CEST)

Illustration fausse ?[modifier le code]

Bonjour, dans la première illustration, on voit que si P = NP alors P = NP-complet, ce qui me semble erroné : tous les problèmes de P ne seraient pas NP-complets ! En particulier les problèmes beaucoup plus simples, comme ceux de NL sont dans P... Je vois que l'illustration vient de la WP anglaise, je reste donc très perplexe, peut-être mes définitions ne sont-elles pas celles de l'article.

Cordialement, --Roll-Morton (d) 25 octobre 2012 à 20:49 (CEST)

L'illustration est bonne. Si P=NP alors P=NP-complet. En effet un problème NP-complet A se ramène alors en temps polynomial à n'importe-quel problème polynomial B, au pire en résolvant l'instance de A en temps polynomial, et en retournant une instance de B qui a la même réponse (on séléctionne à l'avance de 2 instances de B dont une à la réponse oui et l'autre a la réponse non). Je ne sais pas si je suis clair, mais en tous les cas c'est sur il n'y a pas de problèmes. --Pparent (d) 25 octobre 2012 à 23:08 (CEST)
ps: Après il y a différent sens de complétude il s'agit ici de NP-complet au sens des réduction polynomial, pas au sens de réduction logspace... --Pparent (d) 25 octobre 2012 à 23:10 (CEST)

Cela me semble juste, merci pour la réponse rapide !--Roll-Morton (d) 26 octobre 2012 à 14:51 (CEST)

== Relecture de MathsPoetry ==

J'ai demandé à MathsPoetry (d · c · b) si il pouvait, en tant que presque naïf du sujet, faire une relecture critique des articles sur la complexité, voilà sa réponse (sur ma PDD, je copie colle ici) pour cet article ... — TomT0m [bla] 8 février 2013 à 10:22 (CET)


Raté, c'est Problème NP-complet que j'ai relu. Déplacer cette discussion là-bas ?


Bonjour,

Questions volontairement naïves, à ta demande.


A - "Trouver un algorithme polynomial pour un problème NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P = NP ou P ≠ NP"

"P" c'est quoi ? Ce n'est pas encore défini à ce point de l'article. Pas pédagogique. Ajouter au moins "(définis plus loin)".


B - "Tous les algorithmes connus pour résoudre des problèmes NP-complets ont un temps d'exécution exponentiel en la taille de l'entrée dans le pire cas"

Cette phrase me chipote vraiment :

  • est-ce qu'on parle vraiment de l'exponentielle ou c'est juste une façon de parler ? On dit souvent "exponentiel" pour "très rapide" sans vraiment penser à la fonction exponentielle...
Oui c'est vraiment la fonction
  • "tous les problèmes connus" suggère que c'est non démontré, mais qu'on l'a juste constaté expérimentalement. C'est bien ce qu'on veut dire ?
Ça veut dire que pour tous les algorithmes qu'on connaisse, on a démontré qu'ils sont exponentiels (on compte pas les algorithmes dont personne n’a calculé la complexité, par exemple, mais il est peu probable que quelqu'un ait créé un tel algo par accident :) ). Ça ne veut pas dire qu'il n'y ait pas d'algorithme inconnus de complexité meilleure.
  • on a des fonctions qui croissent plus vite que les polynômes, mais moins vite que l'exponentielle, comme . Qu'est-ce qui empêcherait d'avoir une classe de complexité correspondante, ou alors d'avoir des problèmes NP-complets qui soient résolubles dans un temps de cet ordre ?
Rien, si on le savait exactement on aurait une démonstration probablement.
  • cette phrase mériterait vraiment une source...
C'est vrai qu'il n’y a pas beaucoup de source pour cet article, en particulier au début de l’article
intéressant, problème ouvert donc - c'est exponentiel dans les cas qu'on connaît, mais on ne sait pas pourquoi, ni même si c'est forcément vrai, et si on y réfléchit ça aurait de bonnes raisons de pouvoir être hypoexponentiel. Matière à une belle conjecture...
Hey, j'ai pensé tout seul à cette histoire de temps hypoexponentiel sans avoir lu Problème P = NP, ni l'avoir lu nulle part ailleurs ! Ça fait plaisir !!! (je viens de le découvrir dans l'article). --MathsPoetry (d) 8 février 2013 à 12:24 (CET)


C - "Parfois, une modification mineure transforme un problème NP-complet en problème de la classe P. Quelques exemples : . Savoir s'il existe un circuit hamiltonien est NP-complet tandis que savoir s'il existe un circuit eulérien est dans P."

Ça, ça sent l'ânerie. J'ai l'impression que ça sous-entend que le problème du circuit eulérien est un sous-ensemble du problème du circuit hamiltonien. Ce n'est pas vrai, puisque le graphe papillon admet un circuit eulérien et pas de circuit hamiltonien. Évidemment, l'énoncé étant vague, "une modification mineure" peut vouloir dire n'importe quoi, mais au vu des autres exemples on comprend "une restriction". Sinon, avec une modification mineure, déterminer la population de l'Ouganda revient à calculer la distance de la terre à la lune (en effet, il suffit de remplacer "population" par "distance" et "de l'Ouganda" par "de la terre à la lune", modifications évidemment mineures).

Non, c'est une manière, peut être maladroite je sais pas, de dire qu'un petit changement dans la définition du problème, comme changer un plus en un moins, peut parfois complètement changer la complexité du problème. Effectivement on change complètement le problème, en fait.
OK, je disais ça parce que ça venait après deux restrictions à des sous-ensembles. Les graphes eulériens ressemblent énormément dans la définition aux graphes hamiltoniens, mais techniquement ça n'a rien à voir, le "modification mineure" n'est qu'une impression dans ce cas. --MathsPoetry (d) 8 février 2013 à 12:10 (CET)

Et puis, c'est quoi un problème de la classe P ? Tu n'as défini que des langages de la classe P.

Je suis pas vraiment rédacteur de cet article en fait :)


D - Côté pédagogie, on aimerait commencer par des exemples, par exemple de langages déterministes ou non déterministes, même triviaux, puisque tout par de là. De tels exemples ne se trouvent pas non plus dans les articles dédiés.

C'est pas faux.

Je te rappelle que je comprends mal le sujet, donc je n'ai pas besoin de jouer au naïf pour poser de telles questions, ça vient tout seul.


Si tu veux aussi me rendre un service, je veux bien une relecture de l'introduction générale de Graphe hamiltonien et de l'introduction de la section Graphe hamiltonien#Problème du chemin hamiltonien, pour voir si je ne maltraite pas la notion de NP-complétude. J'ai essayé de faire "comme si" il était parfaitement possible que P = NP, donc j'ai soigneusement évité "impossible à calculer", etc.


Cordialement, --MathsPoetry (d) 8 février 2013 à 02:01 (CET)

Cela semble être des remarques sur Problème NP-complet, pas sur cet article ? (J'ai failli avoir une apoplexie quand j'ai lu "C'est vrai qu'il n’y a pas beaucoup de source pour cet article" Sourire) Merci en tout cas à MathsPoetry pour cette relecture (pertinente). --Jean-Christophe BENOIST (d) 8 février 2013 à 10:35 (CET)
Pas beaucoup de source sur les définitions de base /o\ en même temps effectivement elles sont pas forcément supposées se trouver là. — TomT0m [bla] 8 février 2013 à 11:24 (CET)
Rassure-toi Jean-Christophe, il y a bien gourage d'article :-) --MathsPoetry (d) 8 février 2013 à 12:14 (CET)

=> déplacé au bon endroit (si tout est bien cette fois /o\ )

Solution PNP résolue[modifier le code]

J'ai trouvé la solution de PNP, mais le problème personne ne me prend au sérieux quand je veux publier la solution, j'ai contacté plusieurs journaux spécialisé, et pour publier il faut soit être un professeur ou être membre d'un groupe de recherche reconnu. Bref, J'ai la solution et je veux la publier. La solution que j'ai trouvé est: P ≠ NP P =n

Si quelqu'un peut m'aider pour publier la solution je n'attend que ça depuis eux semaines. La solution est sur 20 pages

Merci de votre compréhension, je lance un appel à toute personne capable de m'aider à publier Ma solution P=n.

Khalid El Idrissi de Montréal

Bonjour, wikipédia est une encyclopédie et les pages de discussion sont là pour améliorer les articles pas pour recruter des relecteurs et collègues. Bonne journée.--Roll-Morton (discuter) 27 mai 2014 à 16:56 (CEST)
Bonjour, malheureusement cette démonstration est connue depuis longtemps. Elle a cependant un effet secondaire facheux : toute personne qui l’entend souris, puis passe à autre chose. Elle est donc malheureusement impossible à faire publier, je l’ai déja oubliée. — TomT0m [bla] 27 mai 2014 à 21:38 (CEST)
tentez sur arxiv --Lechewal (discuter) 28 mai 2014 à 13:56 (CEST)
P=n c'est à dire? Clin d'œil. Déja peut-être qu'une première étape serait de publier la démo sur votre page perso, ou un site perso... --Pparent (discuter) 19 octobre 2015 à 02:07 (CEST)

Implications philosophiques sur la nature de la réflexion et de la créativité humaine[modifier le code]

La manière dont est rédigé ce paragraphe me paraît maladroite, car elle semble dire que si l'on démontre P=NP, on démontre la conjecture de Golbach ou l'hypothèse de Riemmann. --Pierre de Lyon (discuter) 2 juin 2016 à 18:55 (CEST)

La rédaction actuelle est : "Une autre implication considérable de la démonstration de P=NP serait qu'il deviendrait envisageable de résoudre une forme réduite du problème de la décision" (avec un conditionnel, en plus). Il n'est pas écrit "serait que l' on résout alors une forme réduite" par exemple. C'est sans doute maladroit, mais que proposes-tu pour augmenter encore d'avantage le conditionnel et la distance ? --Jean-Christophe BENOIST (discuter) 2 juin 2016 à 20:58 (CEST)
J'ai repris la rédaction en présentant d'abord le problème de la décision dans son cas le plus général, puis ensuite dans sa forme réduite. Cependant, je pense que les implications philosophiques sont un peu exagérées.
  1. Les problèmes comme l'arrêt sont indécidables parce qu'ils sont trop complexes à résoudre, donc sans surprise si on se réduit aux problèmes de complexité plus faible que l'arrêt, alors ils sont décidables, on peut descendre encore à NP (ce qui est déjà un choix important), puis à P (si P=NP) (c'est l'objet du débat).
  2. Quand on atteint P, on est loin (très loin) de l'automatisation. Un problème n'est automatisable que s'il est linéaire ou quasi-linéaire. Allez résoudre un problème polynomial de complexité N¹⁰⁰ !
--Pierre de Lyon (discuter) 3 juin 2016 à 15:38 (CEST)
Théoriquement, c'est vrai, bien sûr. Mais en pratique, la plupart des problèmes P sont en O(N3), de même que les algorithmes exponentiels sont plutôt en 2^n qu'en 1,0001^n. C'est bien dommage, mais il se cache sûrement quelque chose de profond là dessous...--Dfeldmann (discuter) 3 juin 2016 à 18:37 (CEST)
Les opinions sur les implications varient selon les auteurs. Certains auteurs ne trouvent pas cela exagéré (ceux en référence, et d'autres) et d'autres trouvent cela exagérés. On peut tout à fait citer les opinions d'autres auteurs. En tout cas, le fait que cela soit un problème du millénaire indique tout de même un penchant vers des implications conséquentes. --Jean-Christophe BENOIST (discuter) 3 juin 2016 à 18:56 (CEST)
Je ne suis pas très sûr de cette dernière remarque : une forte majorité s'attend à ce que P<>NP (et aussi à ce que l'hypothèse de Riemann soit vraie, par exemple) ; les retombées espérées sont plutôt, puisque le problème est si difficile, que les techniques nécessaires pour le résoudre soient nouvelles et utiles ailleurs. Mais je serais surpris qu'on trouve beaucoup d'experts attendant sérieusement (même si P=NP) d'immédiates retombées pratiques (et mes remarques sur Robertson-Seymour visent aussi à signaler qu'on ne gagnera pas grand chose en pratique si on découvre un algorithme linéaire (en A*n) avec A de l'ordre d'un googolplex...)--Dfeldmann (discuter) 3 juin 2016 à 20:11 (CEST)
Cook discute la question en citant (comme moi Fier) . Mais il énonce une thèse de faisabilité comme une assertion défendable. --Pierre de Lyon (discuter) 10 février 2017 à 13:42 (CET)

Fortnow 1[modifier le code]

Dans l'introduction on voit un exposant Fortnow 1 ce qu'aucun commun des mortels ne peut comprendre. Si on insiste on s'aperçoit que cet exposant est en fait cliquable et qu'il s'agit d'une note de fin d'article vers ↑ a et b Paragraphe « What if "P=NP"? », qui est tout aussi cryptique, sinon plus. A mon avis cela ne peut pas rester en l'état et il me semble que nous devrions retourner vers une numérotation classique des notes: 1, 2, 3, etc. S'il s'agit d'une référence à un article, c'est là qu'il faut la donner, s'il s'agit d'autre chose, il faut dire de quoi il s'agit. --Pierre de Lyon (discuter) 2 juin 2016 à 19:10 (CEST)

Tous les AdQ (qui sont une référence) utilisent des appels de notes qui ne sont pas 1, 2, 3 etc.. J'ai pris le premier qui me tombait sous la main : Aqueduc_de_Fontenay par exemple, où les appels de notes sont [Tam 2] ou [Drd1]. Mais je vois ce que tu veux dire, et cet article est le seul où j'ai mis le nom en clair, avant de me rendre compte, non pas que on ne comprenait pas que c'était des appels de notes (ça je ne m'en rend pas compte en effet), mais que c'est simplement assez lourd à la lecture. J'ai fait cet article il y a déjà assez longtemps, et c'était une des premières fois que j'utilisais ce système. Depuis, je me suis stabilisé à un abrégé de deux lettres pour les appels de notes, par exemple dans Passion selon Saint-Jean (les AdQ utilisent 3 lettres). Il est donc tout à fait possible - et même préférable - de raccourcir les références à deux ou trois lettres comme les AdQ, mais pas de revenir à 1,2,3 etc.. Cordialement --Jean-Christophe BENOIST (discuter) 2 juin 2016 à 21:08 (CEST)

Notion d'Oracle[modifier le code]

En ce qui concerne le passage suivant de l'article : "Avec certains Oracles, on peut prouver que P_O = NP_O, et avec d'autres que P_O ≠ NP_O. C'est un résultat auquel on peut s'attendre si le problème P = NP est indécidable, car toute preuve du problème sans Oracle devra pouvoir s'adapter aux cas avec Oracle et donner ces deux résultats différents, ce qui est a priori très difficile, voire impossible.".

Il me semble au contraire que si la décidabilité de P=NP était avérée et la démonstration de P=NP faite, cela impliquerait que la notion d'Oracle est fausse et qu'un raisonnement consistant à écarter une problématique du problème - à l'aide d'un Oracle - car estimant qu'il s'agit d'une problématique extérieure est faux. Le problème est un système, pour le maîtriser il faut en connaître les composantes et les interactions entre ses composantes, si nous en écartons volontairement une c'est tout le système qui est modifié. Quelle est la fiabilité réelle de l'estimation qu'une problématique faisant partie du problème est indépendante de la résolution du problème? Adrix007 (discuter) 21 août 2016 à 03:47 (CEST)

Ces problématiques et ces résultats sont délicats ; il est possible (et l'article tente de le faire) d'exploiter des arguments heuristiques (donc non rigoureux) pour y boir plus clair. Mais lorsque vous déclarer que la notion d'Oracle serait fausse (si...), vous commettez une erreur de catégorie grammaticale (un Oracle est un objet formel ; comment pourrait-il être faux ?) qui rend votre argumentation au minimum non pertinente.--Dfeldmann (discuter) 21 août 2016 à 08:12 (CEST)
Conflit d’édition Ce n'est pas "au contraire", c'est "en effet". En effet, si la décidabilité de P=NP était avérée et la démonstration de P=NP faite (ou celle de P≠NP d'ailleurs), cela impliquerait que la notion d'Oracle est fausse, ce qui est précisément la raison pour laquelle on pense que cette démonstration avec les oracles est un fort indice, voire une preuve, de l'indécidabilité du problème. La notion d'Oracle ne serait alors pas forcément fausse d'ailleurs, mais la situation serait très difficile, et il faudrait apprendre à maitriser cette notion, tout comme Cauchy (ou Weierstrass je ne sais plus) a légiféré les sommes infinies de suites par exemple. Je ne vois pas non plus pourquoi vous parlez de "problématique extérieure écartée"; il n'y a pas du tout cette notion dans le raisonnement. Cordialement --Jean-Christophe BENOIST (discuter) 21 août 2016 à 08:23 (CEST)
@Dfeldmann, il ne faut pas prendre "faux" au pied de la lettre mais dans le sens "si l'utilisation d'un objet formel introduit une contradiction logique, alors il y a qqchose de "faux" dans cet objet formel, soit la notion elle même (qui est incompatible avec le système formel), soit dans son mode d'utilisation". --Jean-Christophe BENOIST (discuter) 21 août 2016 à 08:32 (CEST)
Tout à fait, mais il n'y a pas là de contradiction logique, seulement un résultat contre-intuitif (et réfutant un argument heuristique) à savoir que les problèmes proches P_O=NP_O pourraient être vrais, faux ou indécidables suivant O, alors qu'on aurait démontré P=NP. Disons que cela montrerait que la notion d'Oracle est mal adaptée à ce qu'on veut en faire ici, puisque elle prédirait un résultat faux, et que cela amènerait en effet à chercher à définir une notion d'Oracle plus fine.--Dfeldmann (discuter) 21 août 2016 à 08:39 (CEST)

Un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP.[modifier le code]

Si quelqu'un démontre que P=NP est indécidable dans ZFC, gagnera-t-il un million de dollars? --Pierre de Lyon (discuter) 28 janvier 2017 à 19:16 (CET)

D'après Gasarch, l'indépendance vis-à-vis de ZFC est aussi une réponse (celle de 4 scientifiques interrogés par lui). Donc la question est mal formulée dans l'article. --Pierre de Lyon (discuter) 10 février 2017 à 13:34 (CET)
Ca parait assez marginal, très artificiel et peu clair sur le fond : pour ce genre de démonstration on ne se soucierait pas, au moins dans un premier temps, de savoir si on a besoin ou non d'un inaccessible par exemple. L'article donne déjà une place démesurée à ces questions d'indécidabilité. Proz (discuter) 10 février 2017 à 21:26 (CET)
Je suis d'accord sur le fait que l'artcile donne un part démesurée à l'indécidabilité (indépendance). C'est parce qu'on en parle (trop?) que je pense qu'on ne peut pas dire que c'est simplement P=NP ou P≠NP. --Pierre de Lyon (discuter) 11 février 2017 à 09:48 (CET)
On pourrait dire que ce n'est pas simplement P=NP ou P≠NP à la façon de la dernière phrase de http://www.claymath.org/millennium-problems/rules-millennium-prizes ? Proz (discuter) 11 février 2017 à 11:57 (CET)

Présentation formelle[modifier le code]

Je pense que la présentation formelle, telle qu'elle apparaît ici, est inutile dans Wikipédia.

  1. P=NP n'est pas lié spécifiquement aux machines de Turing, donc il 'agit d'une présentation possible, mais pas consensuelle.
  2. Si quelqu'un cherche une présentation, il ira la chercher dans un livre.
  3. Peu de (aucun) lecteurs liront (lira) cette section.

--Pierre de Lyon (discuter) 28 janvier 2017 à 19:28 (CET)

Hum, oui ça ne me parait pas très pertinent, mais je connaissais le sujet avant, il faudrait des avis extérieurs. Le seul public qui me semble visé est celui des matheux qui ne connaissent pas le sujet, sont un peu échaudés par le coté flou et « sensationnel » (par rapport à un article de maths classique), et sont rassurés de voir des symboles. --Roll-Morton (discuter) 29 janvier 2017 à 13:08 (CET)
C'est vrai que c’est pas très lisible en l’état… Par contre je ne pense pas que ce soit une « bonne attitude » de dire « je fais des maths donc je mets des symboles ésotériques », certes c'est utile pour faire comprendre que ce qu’on fait n’est pas juste de la cuisine, mais j’ai l’impression que cette section donne l’idée qu’elle est « importante » parce qu’il « y a des maths dedans ». Et autant faire comprendre que c’est formel et rigoureux est une bonne chose, autant appuyer l’intérêt dessus… Mais bon, doit bien y avoir moyen de reformuler ça de manière plus digeste :-D Fabrice Mouhartem (discuter) 7 février 2017 à 10:04 (CET)
Je n'ai pas d'avis sur la question, mais pour répondre à Pierre de Lyon, dans sa définition officielle P=NP est spécifiquement lié aux machines de Turing. (La dite section est d'ailleurs directement tirée de cette définition officielle, bien que sûrement moins claire).--Pparent (discuter) 7 février 2017 à 10:09 (CET)
Si P=NP était spécifiquement lié aux seules machines de Turing, ce problème n'aurait pas l'importance qu'il a. Le problème P=NP est intrinsèque et ne dépend pas du modèle de calcul. --Pierre de Lyon (discuter) 7 février 2017 à 16:14 (CET)
Ce problème a l'importance qu'il a car les ordinateur actuels, et les machine de Turing sont équivalentes. Dans le sens ou une machine de Turing peut émuler un ordinateur moderne, et un ordinateur moderne peut émuler une machine de Turing. Il n’empêche que le problème P=NP se pose dans le cas des machine de Turing, c'est très important, et bien sur que c'est dépendant du model de calcul. Par exemple les ordinateurs quantique ne sont pas équivalant à une machine de Turing, et le problème transposé dans ce cadre n'aurait pas forcement la même réponse. De même que les cas ou on travaille sur des machine de Turing avec oracle (un autre model de calcul), les résultats sont différent (voir article). --Pparent (discuter) 10 février 2017 à 12:08 (CET)
Merci d'avoir précisé ce que je voulais dire. Le problème P=NP se pose dans les modèles de calcul de la thèse de Church, qui correspondent à une multitude de modèles de calcul équivalents. Il n'y a donc pas lieu de privilégier l'un des modèles, par exemple un certain type de machine de Turing (il y en a beaucoup de variantes: une bande, plusieurs bandes, bande infinie dans les deux sens etc.) parmi ceux-là, ce que ne fait pas Cook, qui pose, à juste titre, le problème en termes de langages, donc de façon indépendante d'un modèle spécifique. Ceci dit, les machines à oracle ne sont pas considérées comme un modèle de calcul au sens commun du terme. En revanche, les ordinateurs quantiques, constituent un modèle « alternatif ». --Pierre de Lyon (discuter) 10 février 2017 à 12:45 (CET)
En fait pour définir un problème mathématique, il faut bien choisir des termes précis de sa définition. Hors la définition officielle rédigée par cook se base clairement sur les machines de Turing classiques. Lire absolument la absolument la ref [ http://www.claymath.org/sites/default/files/pvsnp.pdf ]. Il s'agit de la définition officielle de l'institue Clay qui offre le million, et il s'agit clairement de Machine de Turing classique (Cook donne en référence le papier de la définition initiale par Turing). Donc je ne vois pas trop ou est le débat... (les machines de Turing avec oracle sont bien modèle de calcul, bien qu'on ne puisse pas les implémenter dans le monde réel pour la plus-part, certaines si comme les oracles générateur aléatoire) --Pparent. . (discuter) 17 février 2017 à 11:24 (CET)
Le fichier pvsnp.pdf ne constitue pas une définition « officielle », mais un lien vers un article que Cook a écrit sur le sujet pour résumer la problématique. J'en extrais deux phrases: « Informally the class P is the class of decision problems solvable by some algorithm within a number of steps bounded by some fixed polynomial in the length of the input. » et « Thus P is a robust class and has equivalent definitions over a large class of computer models ». --Pierre de Lyon (discuter) 17 février 2017 à 17:49 (CET)
http://www.claymath.org/millennium-problems/p-vs-np-problem Voir sur la droite "Official problem description". Désolé je ne souhaites pas faire de cela un débat personnel, juste rechercher la vérité. Ayez l'assurance de toute ma bienveillance, et respect pour votre travail. Clin d'œil. --Pparent (discuter) 17 février 2017 à 18:37 (CET)
Aussi désolé d'avoir à préciser cela, mais la thèse de church, concerne l'équivalence de modèles de calculs au sens de la calculabilité, et donc lorsque l'on ne prend pas en compte les quantités de ressources (mémoire, temps). Or le problème P=NP se base sur l'étude de la quantité de ressources, donc la thèse de Church ne s'applique pas. D'ailleurs on peut définir P et NP de manière équivalent sur deux modèles de calculs ( P="ensemble des problèmes solvables en temps polynomial sur une machine de Turing déterministes", NP="ensemble des problèmes solvables en temps polynomial sur une machine de Turing non-déterministes" ). Par exemple si dans la présentation formelle on remplace machine de Turing "deterministe" par "non-deterministe", alors il est simple selon cette définition de montrer que P=NP. Donc je suis désolé, mais on ne peut pas laisser "P=NP ne dépend pas d'un modèle de calcul particulier", car pour moi ça n'est pas exacte. Si d'autres personnes peuvent apporter leurs avis, ça serait bien! Merci Clin d'œil --Pparent (discuter) 18 février 2017 à 11:25 (CET)
J'ai l'impression que tout le monde a un peu raison. Ce que Pierre veut dire, je crois, est qu'il existe un grand nombre de modèles de calcul strictement équivalents à des machines de Turing déterministes, et que P=NP est pertinent dans tous ces modèles de calcul. Là où tu as raison, c'est que la thèse de Church va en effet au delà des MTD et inclue des modèles de calculs où P=NP n'est pas pertinent (notamment les classes BPP et BQP, qui sont issues de modèles de calculs équivalents au sens calculabilité aux MTD, mais pas équivalent au sens classe de complexité). Donc il y a en effet une précision à apporter : les classes P, NP, sont définies à partir des MTD (et modèles de calcul strictement équivalent, pas au sens de Church), comme je crois le lambda calcul. Mais comme les classes P et NP sont à 99.999% définies à partir des MTD il est évident que WP doit présenter les choses de cette manière également, et je ne sais pas si cela vaut la peine de rentrer dans la complication et subtilité d'expression pour dire que c'est pertinent dans d'autres modèles de calculs, mais pas tous au sens de Church. --Jean-Christophe BENOIST (discuter) 18 février 2017 à 12:15 (CET)
Je viens de voir que Notification Proz : vient de mettre à jour dans une direction qui ne va pas de le sens des deux dernières interventions. La nouvelle formulation est est que P=NP peut-être posé dans tout "modèles de calcul [qui] permettent de définir une notion de fonction calculable". Or, une machine de Turing quantique "permet de définir une notion de fonction calculable" (qui est exactement celle des MTD = thèse de Church), mais pourtant, est-ce un modèle de calcul permettant de poser P=NP ? Certes, BQP=P probablement, mais ce n'est pas certain. --Jean-Christophe BENOIST (discuter) 18 février 2017 à 20:48 (CET)
Ce n'est pas ce que j'ai voulu écrire : il est assez évident que l'on peut fabriquer (artificiellement certes) un modèle de calcul Turing complet qui n'est pas simulable en temps polynomial par une machine de Turing ou autre. Je corrige. Proz (discuter) 18 février 2017 à 20:53 (CET)
Bon j'ai précisé, mais ça n'est pas forcément heureux car ça conduit à parler prématurément de temps polynomial, et je conteste avoir changé dans la direction que donne JCB, s'il y avait ambiguïté elle était déjà présente. J'ai voulu corriger au départ car c'est la notion de fonction calculable qui est correspond à ce qui est calculable sur un ordinateur moderne, pas le modèle de calcul (et Cook ne dit pas autre chose).
J'ai essayé de rendre la présentation, qui en rajoutait dans le formalisme, plus lisible. Par ailleurs cette présentation par "projection" est assez indépendante du modèle de calcul en réalité. Maintenant sur le fond (faut-il laisser ce paragraphe) : on n'a besoin d'une telle présentation dès que l'on veut démontrer des théorèmes (comme celui de Cook). Ici il n'est pas forcément indispensable, mais je pense qu'on peut encore la peaufiner, pour que finalement ça dépende très peu du modèle choisi, et que ça donne malgré tout une idée plus claire que la présentation informelle (en particulier la projection par un quantificateur borné polynomialement ce qui n'apparaît pas dans la présentation informelle). Proz (discuter) 18 février 2017 à 21:22 (CET)
Comme dit ci-dessus "je ne sais pas si cela vaut la peine de rentrer dans la complication et subtilité d'expression pour dire que c'est pertinent dans d'autres modèles de calculs, mais pas tous au sens de Church", et Pparent semble être du même avis. Je n'ai pas trouvé de source qui rentre dans cette complication (si cela était le cas, on aurait une bonne formulation, sourcée), et toutes s'en tiennent strictement aux MTD (mais si on trouve une source qui ce serait intéressant). Les machines de Turing quantique ne sont pas un exemple "artificiel" de construction d'un modèle de calcul Turing complet qui n'est pas simulable en temps polynomial (enfin si BQP > P, ce dont on ne sait rien, mais ce qui est très possible) --Jean-Christophe BENOIST (discuter) 19 février 2017 à 16:00 (CET)
D'où la référence aux ordinateurs actuels (pas encore de machine quantique), par contre si on pouvait éviter de dire qu'un modèle de calcul peut être équivalent à un ordinateur... Pa à chercher loin pour une source, tout ce qu'il y a à dire (inutile de faire référence à la thèse de Church) est à la première page de l'article de Cook donné en référence qui parle bien d'autres modèles et cite explicitement celui-ci machine RAM. Proz (discuter) 20 février 2017 à 01:06 (CET)

Je voudrais citer deux phrases de Cook dans l'article appelé "définition officielle": Thus P is a robust class and has equivalent definitions over a large class of computer models. Here we follow standard practice and define the class P in terms of Turing machines. --Pierre de Lyon (discuter) 2 mars 2017 à 22:30 (CET)

Je suis parfaitement d'accord, et c'est du reste ce que je disais ci-dessus : "Ce que Pierre veut dire, je crois, est qu'il existe un grand nombre de modèles de calcul strictement équivalents à des machines de Turing déterministes, et que P=NP est pertinent dans tous ces modèles de calcul." Mais cela n'empêche pas la remarque de Pparent. --Jean-Christophe BENOIST (discuter) 2 mars 2017 à 22:50 (CET)
En fait Cook dit que le problème peut être posé de manière équivalente sur un grand ensemble de modèles de calculs équivalents (au sens de l'émulation en temps polynomial et non de la thèse de Church), ce avec quoi je suis d'accord comme je l'ai dit depuis le début (= modèle de calcul équivalent aux ordinateur actuels), mais ça ne veut pas dire que ça peut être posé sur tous les modèles de calculs, et donc que ça serait indépendant du modèle, comme on en déjà donné des contre-exemples (machine de Turing non-deterministes, machines quantiques, ect...). --Pparent (discuter) 3 mars 2017 à 01:26 (CET)

Indécidabilité avec oracle.[modifier le code]

Merci Notification Jean-Christophe BENOIST : pour avoir corrigé si rapidement la source. Il est affirmé effectivement par Delaye 2005 que P = NP relativisé à un oracle aurait été démontré indécidable dans certains cas en théorie des ensembles (sans autre précision) par T. Baker, J. Gill et R. Solovay en 1975. Il ne peut s'agir que de cet article http://epubs.siam.org/doi/abs/10.1137/0204037 voir http://137.226.34.227/dblp/db/indices/a-tree/s/Solovay:Robert.html . Or cet article ne parle nulle part de non-démontrabilité. Il montre les résultats de la première partie de l'encadré de Delahaye (des oracles pour lesquels on a P=NP, d'autres P!= NP), et d'autres plus fins du même genre (peut-être Notification Pierre de Lyon : peux-tu confirmer ?).

Je suis étonné de ce résultat (même s'il est énoncé de façon assez imprécise, de quelle nature est l'oracle ?). Les oracles de Baker, Gill et Solovay sont décidables (récursifs). Si l'oracle est décidable ou même arithmétique, ce serait un résultat tout à fait nouveau (cf. http://www.scottaaronson.com/papers/pnp.pdf p 26-27). Sinon ça n'aurait probablement plus grand rapport avec P=NP classique.

Je ne le vois pas le résultat cité ailleurs, donc je pense qu'il faut être prudent, la source donnée n'est pas suffisante. Proz (discuter) 11 février 2017 à 12:30 (CET)

Je pense que des sources ont repris le résultat de 1975 pour estimer que "ce résultat est considéré comme un indice en faveur de l'idée que P = NP est indécidable dans la théorie des ensembles", même si le résultat lui même ne le dit pas. C'est ce que laisse entendre JPD, et même il laisse entendre que plusieurs sources le considèrent. Je crois comprendre ce qui est arrivé avec les sources sur ce point. En fait la véritable source visée par "Is P Versus NP Formally Independent?" était [4], où le paragraphe 3.1 (Oracles) colle. Je vais corriger la source dans l'article.
Après, il faut voir la WP:Proportion du sujet de l'indécidabilité dans l'ensemble des sources en effet. On voit que Aaronson en parle aussi et y consacre même un article entier. Je pense qu'il faut plutôt augmenter l'article sur la partie "pourquoi la preuve de P=NP est difficile", qui n'est pas assez développée, en parlant des preuves naturelles etc.., ce qui diminuera mécaniquement la WP:Proportion du sujet de l'indépendance dans l'article, en la rendant très inférieure à la Proportion qu'y accorde JPD lui-même dans son article général sur P=NP.
Actuellement le sujet occupe 5k/36k ~= 14% de l'article, ce qui ne semble pas déraisonnable, et encore moins si on développe la difficulté de la preuve ou d'autres sujets. --Jean-Christophe BENOIST (discuter) 11 février 2017 à 14:29 (CET)
Ca y est, merci pour la bonne référence, effectivement c'est bien démontré, et avec un oracle décidable (ce que j'ai écris au dessus est faux tel quel) mais par Hartmanis et Hopcroft en 1976 en s'appuyant sur Baker, Gill et Solovay 1975. Ca fonctionne pour n'importe quel système d'axiomes cohérent avec les conditions habituelles du th. de Gödel. C'est une méthode astucieuse mais de style Gödel ou plutôt Gödel-Rosser avec une machine et un oracle tout à fait ad hoc. Hartmanis et Hopcroft écrivent "it does not say anything directly about the classic P = NP problem", et effectivement je comprends mal comment ça pourrait en dire quoi que ce soit vu la méthode de démonstration utilisée (donc je reste étonné de ce qu'écrit Delahaye). Le résultat de Baker, Gill et Solovay 1975 dit bien quelque chose sur la difficulté de la preuve (elle ne peut pas passer aux machines avec oracles). Proz (discuter) 12 février 2017 à 01:00 (CET)
Merci à toi d'avoir relevé le problème de sources ! C'est peut-être une opinion personnelle de JPD (de considérer que ces résultats disent - indirectement - quelque-chose sur l'indépendance de P=NP), bien qu'il ne la formule pas ainsi. Je te (vous avec les autres suiveurs de cette page) laisse voir s'il est opportun de le supprimer ou de le formuler autrement, bien que l'avis de JPD ne soit pas négligeable, et que Aaronson cite également ces résultats dans le contexte du problème de l'indépendance. --Jean-Christophe BENOIST (discuter) 12 février 2017 à 11:18 (CET)
Nous pouvons laisser la citation de JPD en la nuançant comme vous venez de le discuter. --Pierre de Lyon (discuter) 14 février 2017 à 10:54 (CET)

Proposition d'anecdote pour la page d'accueil[modifier le code]

Une proposition d'anecdote pour la section « Le Saviez-vous ? » de la page d'accueil, et basée sur cet article, a été proposée sur la page dédiée.
N'hésitez pas à apporter votre contribution sur la rédaction de l'anecdote, l'ajout de source dans l'article ou votre avis sur la proposition. La discussion est accessible ici.
Une fois l'anecdote acceptée ou refusée pour publication, la discussion est ensuite archivée .
(ceci est un message automatique du bot GhosterBot le 26 septembre 2017 à 15:46, sans bot flag)

l'anecdote en question est : "Démontrer que P = NP permettrait de trouver facilement la solution de tous les autres problèmes du prix du millénaire.". Elle a soulevé quelques remous : voir Discussion Wikipédia:Le saviez-vous ?#P=N/P, Wikipédia:Le_Bistro/21_février_2018#Le_saviez-vous_?_Anecdote_à_vérifier.. C'est vrai qu'une boutade (assez contestable d'ailleurs, même avec l'explication, mais c'est clairement une boutade) devient dans notre article une vérité immanente, une fois extraite du contexte et énoncée avec toute la componction du "ton encyclopédique" et c'est encore amplifié quand c'est résumé en une phrase. Sur un tel sujet est qu'il y a une telle quantité de choses écrites que l'on y trouve à peu près tout et n'importe quoi, et ce n'est pas facile d'en extraire quelque chose de correct, notre article a tendance à accorder une importance démesurée aux choses les plus marginales. Sur cet exemple précis je propose déjà de l'enlever du RI, et bien sûr la référence "slate" manifestement inspirée elle-même de wikipedia est à éliminer immédiatement. Proz (discuter) 22 février 2018 à 20:21 (CET)
Disons qu'il faudrait conserver dans le RI un résumé des enjeux les plus importants de la démonstration de P=NP (et aussi de P<>NP). Mettre un autre exemple ne pose pas de problème, mais entre Fortnow, Cook, Delahaye et sans doute bien d'autres cet exemple est assez souvent cité et a, à tort ou à raison, une assez grande WP:Proportion parmi les exemples cités de conséquence de P=NP et il faudrait le réintégrer dans le corps de l'article, sans en faire des tonnes ni le censurer. --Jean-Christophe BENOIST (discuter) 23 février 2018 à 00:21 (CET)
Toute la question est que le propos est actuellement mis hors contexte et clairement déformé : Cook parle d'un algorithme efficace pour un problème NP-complet, et pas seulement de P = NP, Fortnow aussi d'ailleurs qui l'ajoute comme hypothèse en début de §, c'est plus facile d'être circonstancié dans le corps de l'article. Proz (discuter) 23 février 2018 à 02:15 (CET)
Pourquoi pas, mais il ne faut pas renoncer à résumer qqchose, et autre chose, dans le RI concernant P=NP même si cela mène à quelques approximations, presque inévitables dans un RI. Par exemple la crypto. Sinon le conditionnel, comme je l'ai rajouté hier, est conforme à des hypothèses conditionnelles supplémentaires à la démo de P=NP. --Jean-Christophe BENOIST (discuter) 23 février 2018 à 08:45 (CET)

P = NP et cryptogaphie[modifier le code]

Le problème de la factorisation d'un nombre (autrement dit le cassage de RSA) n'est pas NP-complet. Je propose d'enlever les références à ce problème dans l'article. --Pierre de Lyon (discuter) 21 décembre 2017 à 12:09 (CET)

Le problème n'est peut-être pas NP-Complet (mais il l'est peut-être, on ne sait pas), mais il est assurément NP. P=NP ne concerne pas seulement les problèmes NP-Complets. Non ? La subtilité est que si P!=NP cela ne veut pas dire que RSA est incraquable. Mais si P=NP et que on trouve l'algo polynomial, il l'est si on a une puissance suffisante. Mais justement, c'est cité dans les conséquences de P=NP. On retrouve cet exemple dans de nombreuses sources (par exemple ici). --Jean-Christophe BENOIST (discuter) 21 décembre 2017 à 13:09 (CET)
Je suis d'accord, la factorisation est un archétype de problème NP. Mais il faudrait dire ce que tu dis d'une manière ou d'une autre. Note que je n'ai touché à rien. Si vous pensez qu'il faut laisser cela en l'état, j'aurais au moins posé le problème. --Pierre de Lyon (discuter) 21 décembre 2017 à 14:49 (CET)
Mais justement je ne voyais pas très bien le problème posé. C'était le fait que P!=NP ne garantit pas RSA car la factorisation n'est pas assez "difficile" pour être NP-Complet ? Si c'est cela on peut le dire en effet, sans oublier que on n'est pas dans les conséquences de P!=NP, mais les conséquences de P=NP. --Jean-Christophe BENOIST (discuter) 21 décembre 2017 à 15:04 (CET)

C'est dur ? C'est sûr ?[modifier le code]

Bonjour à tous,

Oui, c'est sûr, il est dur, cet article. En tout cas pour moi, mais ça n'intéresse probablement pas grand monde. Ce qui m'amène ici, c'est l'emploi de "dur" dans la section "Importance" : [...] dont les problèmes sont au moins aussi durs que tous les problèmes de NP, autrement dit les problèmes les plus durs de NP [...] Je me demande si c'est un terme admis des matheux, ou une facilité du langage courant pour complexe, ou autre terme à trouver. Voila, je vous laisse avec ce cadeau, pour moi, c'est trop aventureux, comme terrain.

Cordialement, et Hop ! Kikuyu3 Sous l'Arbre à palabres 15 avril 2018 à 18:33 (CEST)

J'ai longtemps réfléchi à une traduction adéquate de « hard » et je n'en ai pas trouvée de meilleure que « dur », même s'il a son côté familier que n'a pas « complexe », qui d'ailleurs n'est pas une bonne traduction de « hard ». En effet, « complexe » existe aussi en anglais. Ceci dit, quoiqu'on fasse certaines parties techniques de l'article resteront dures à lire Sourire. --Pierre de Lyon (discuter) 16 avril 2018 à 09:02 (CEST)
Cela dit, la question de Kikuyu était plutôt sur la définition de "dur". J'ai toujours compris ce terme comme étant équivalent à "de complexité supérieure à polynomiale" (exponentielle notamment), mais je n'ai pas réussi à trouver une définition réellement officielle. A-t-on une source ? Ce serait pas mal de faire un article court sur le terme. --Jean-Christophe BENOIST (discuter) 16 avril 2018 à 09:31 (CEST)
Hein ? Il me semblait que la traduction française était plutôt "NP-difficile". Je me trompe ?--Dfeldmann (discuter) 16 avril 2018 à 09:37 (CEST)
Oui, c'est cela qui est derrière la phrase citée par Kikuyu. "Aussi dur" => réductible par réduction polynomiale. Mais il faut à un moment relier "dur" à la notion de complexité, car sinon comment définit-on les problèmes "les plus durs" sinon par leur complexité temporelle ? --Jean-Christophe BENOIST (discuter) 16 avril 2018 à 10:01 (CEST)
C'est vrai que « difficile n'est pas mal, mais plus long et moins fidèle. --Pierre de Lyon (discuter) 16 avril 2018 à 11:30 (CEST)

Leonid Levin[modifier le code]

Dans quel article Leonid Levin a-t-il publié sa présentation du problème P=NP ? --Pierre de Lyon (discuter) 18 avril 2018 à 10:35 (CEST)

A priori, l'article ne dit pas qu'il a présenté le problème P=NP, mais qu'il a montré que le problème SAT est NP-complet. C'est la seule allusion à Levin dans cet article. --Jean-Christophe BENOIST (discuter) 18 avril 2018 à 11:09 (CEST)
En fait, d'après ce que je sais, Levin a montré qu'un problème de pavage est NP-complet, ce qui suppose d'avoir plus ou moins énoncé le problème P=NP. --Pierre de Lyon (discuter) 18 avril 2018 à 11:59 (CEST)