Discussion:Problème NP-complet

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)

---

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 $y=k\cdot e^{x}$ 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 $n^{log(n)}$. 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)

NP vs EXPTIME

Il me semble que cette phrase est même fausse. Prenez un problème NP-complet et un programme qui le résout en temps $C.2^{n}$. Transformez-le par padding pour qu'il n'accepte que des entrées de taille $n^{2}$ où $n$ est la taille de l'entrée initiale. Sa complexité en temps est maintenant bornée par $C'.2^{n/2}$, ce qui n'est pas dans EXPTIME. Pourtant, il est encore NP-complet: il suffit de prendre une reduction de SAT vers le problème initial et de rajouter le padding, ce qui se fait en temps polynomial et la réduction est encore polynomiale. Pintoch (discuter) 25 juillet 2014 à 12:32 (CEST)

Huh ? $C'.2^{n/2}=C'({\sqrt {2}})^{n}=C2^{p(n)}$, où p est un polynôme ; quelle que soit la définition que tu prends de EXPTIME, je vois pas le problème...--Dfeldmann (discuter) 25 juillet 2014 à 13:02 (CEST)

Oulah oui tu as raison. La phrase n'en reste pas moins fausse selon l'article anglais. Pintoch (discuter) 26 juillet 2014 à 11:36 (CEST)

NP est inclu dans EXPTIME, donc la phrase est juste "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". Cela dit, il faudrait peut-être reformuler la phrase, car on peut manquer effectivement la fin de la phrase. --Jean-Christophe BENOIST (discuter) 26 juillet 2014 à 12:16 (CEST)

Encore une fois, je peux me tromper, mais il me semble que la phrase suivante implique le contraire: "For example, the Independent set and Dominating set problems are NP-complete when restricted to planar graphs, but can be solved in subexponential time on planar graphs using the planar separator theorem." Il existerait donc un algorithme résolvant un problème NP-complet en temps sous-exponentiel (sans être polynomial j'imagine). Pintoch (discuter) 26 juillet 2014 à 13:38 (CEST)

Mmmm... Si NP était inclus dans SUBEXP, car il existe un algo NP-Complet SUBEXP, cela serait un scoop ! Il y a qqchose qui cloche, probablement côté de la phrase anglaise. Mais il faut éclaircir cela en effet. --Jean-Christophe BENOIST (discuter) 26 juillet 2014 à 14:32 (CEST)

(conflit de modification) Si c'était vrai, par réduction, tous les problèmes NP (complets ou non) seraient résolubles en temps sous-exponentiel... J'ai du mal à le croire. L'article anglais sur "independent set" ne dit d'ailleurs pas cela, et remarque quelque chose de très intéressant, en revanche : deux problèmes NP-complets, qui, par définition, prennent (à un polynôme près) le même temps pour le pire cas, peuvent d'une part avoir des temps très différents pour certains cas favorables, d'autres part des temps très différents pour la recherche de solutions "approchées".--Dfeldmann (discuter) 26 juillet 2014 à 14:37 (CEST)

Pour moi il n'y a aucun problème avec cette phrase. Même si elle n'est pas "vraie en absolue", mais seulement vraie pour l'instant. Car il suffit que quelqu'un trouve un algo sous-exponentiel pour un problème NP-Complet pour qu'elle devienne fausse. --Pparent (discuter) 26 juillet 2014 à 15:31 (CEST)

Mais c'est justement ce que semble dire la phrase en anglais donnée par Pintoch, qu'il faut élucider. Je pense que le pb est du côté de la phrase en anglais. --Jean-Christophe BENOIST (discuter) 26 juillet 2014 à 16:00 (CEST)

Une fois donnée la partition grâce au Planar Separator Theorem, le problème est de complexité sous exponentielle. Mais la recherche de la partition est évidement un problème NP-Complet... source : NP-completeness of the Planar Separator Problems, Article in Journal of Graph Algorithms and Applications 10(2):317-328 · January 2006 GracchusB (discuter)

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)

---

PS. Cette discussion attéri ici après moultes rebondissements /o\ — TomT0m ^[bla] 8 février 2013 à 12:59 (CET)

Bonjour,pour ce qui est de la définition de P, j'ai fait l'article sur cette classe, mais il n'est pas très développé et il faut de toute façon redefinir rapidement le truc ici. J'ai remarquer qu'il n'y a pas de page pour NP, mais que celle-ci (NP-complet) existe ce qui me semble un peu bizarre. Peut-être peut-on faire deux articles séparés (NP pourrait parler plus de structure, de classe etc. et NP-complet plus de problèmes, méthode de résolutions)--Roll-Morton (d) 8 février 2013 à 14:20 (CET)

NP difficile versus NP complet

NP-difficile redirige ici, mais il me semble bien qu'un problème C-difficile et un problème C-complet ont des définitions différentes : un problème C-difficile n’est pas forcément dans C, tandis qu'un problème C-complet est dans C. C'est confirmé par en:Complete_(complexity). — TomT0m ^[bla] 16 mai 2013 à 18:37 (CEST)

C'est vrai, mais on n'a pas grand chose à dire sur les problèmes NP-difficile, difficile d'en faire un article. Zandr4^[Kupopo ?] 16 mai 2013 à 18:53 (CEST)

Faudrait pas non plus laisser entendre par la redirection que ce sont des synonymes, donc lever l’ambiguité dans l’intro est important (cela dit c'est aussi rapide de le faire que de taper la parenthèse, mais j’ai la flemme, donc bookmark /o\). — TomT0m ^[bla] 16 mai 2013 à 19:02 (CEST)

J'ai créé un article court ; il me semble que l'on est pile dans le cas de figure pour lesquels ils sont utiles.--Gokimines (discuter) 19 janvier 2018 à 23:51 (CET)

Heuristiques

D'où vient l"affirmation que les heuristiques ne donnent pas de solutions exactes? Commet doit-on appeler une méthode de calcul qui donnent une solution exacte et qui n'est pas algorithmique? Cela s'appelle une heuristique. Je me suis donc permis de revenir à la phrase que j'avais écrite. --Pierre de Lyon (d) 23 mai 2013 à 17:52 (CEST)

Euh... C'est quoi une méthode de calcul qui n'est pas algorithmique ? Ordinairement, algorithme = méthode de calcul. Zandr4^[Kupopo ?] 23 mai 2013 à 17:59 (CEST)

Quoi qu'il en soit, si tu n'es pas d'accord avec la définition d'heuristique, il faut aussi modifier l'article Heuristique (mathématiques). Zandr4^[Kupopo ?] 23 mai 2013 à 18:03 (CEST)

La dernière fois que j’ai demandé sa définition d'algorithme à Pierre, je me suis fait traiter de troll . Je suis quand même curieux de l’avoir, parce que j’ai un peu la même impression de sa part. — TomT0m ^[bla] 23 mai 2013 à 18:10 (CEST)

Dans le contexte de l'informatique théorique une heuristique est un algorithme qui donne des solutions réalisables, et dont on espère qu'elle sont bonnes, mais pas forcement optimale. Il suffit de chercher un tout petit peu sur internet pour ce rendre compte que c'est la définition communément utilisée d'une heuristique. --Pparent (d) 23 mai 2013 à 21:11 (CEST)

Je serais curieux très curieux d'apprendre à propos de ces techniques non-algorithmiques qui donnent des solutions exactes. C'est quoi comme technique? Une boule de cristal USB? --Pparent (d) 23 mai 2013 à 21:15 (CEST)

Le terme heuristique est aussi employé pour les choix non triviaux de variables à brancher dans les algorithmes de backtracking (recherche arborescente) ou dans un algorithme comme algorithme A*, ou certains algorithme de jeux. Dans ce cas le choix peut influencer beaucoup les performances de l’algorithme, et la définition qu'on m’avait donné était un truc très général du style n'importe quel moyen d'accélérer la résolution d'un problème (on peut se ramener à l’optimisation en posant le problème du choix optimal d'une variable ou d'un noeud dans l’agorithme, et qu’on a en général pas de moyen de faire ce choix optimal de manière sure, on utilise donc une heuristique). — TomT0m ^[bla] 23 mai 2013 à 21:33 (CEST)

Le voyageur de commerce est-il NP-complet ?

Une phrase me pose problème :

Bien qu'on puisse vérifier rapidement toute solution proposée d'un problème NP-complet, on ne sait pas en trouver efficacement. C'est le cas, par exemple, du problème du voyageur de commerce ou de celui du problème du sac à dos.

Cette phrase laisse penser que le problème du voyageur de commerce est NP-complet. Sans précision particulière, ce que l'on appelle "problème du voyageur de commerce" consiste habituellement à trouver un circuit hamiltonien de poids minimal. A ma connaissance, ce problème est NP-difficile mais pas NP-complet. Si on a circuit hamiltonien, on ne peut pas vérifier efficacement qu'il est de poids minimal. Le problème n'est pas NP et donc cette phrase me semble erronée.

Par contre, un problème voisin de celui du voyageur de commerce est : étant donné un poids M, existe-t-il un circuit hamiltonien de poids inférieur ou égal à M ? Dans ce cas-là, le problème est effectivement NP-complet.

Donc je verrais deux possibilités :

- soit supprimer la phrase posant problème

- soit préciser ce que l'on entend exactement par "problème du voyageur de commerce"

Bonjour, il ne faut pas confondre un problème dans sa version optimisation, et dans sa version décision. De manière standart les classe P et NP, et par extention NP-Complet, sont définit pour des problèmes de décision. Quand on dit que le voyageur de commerce est NP-complet il est donc sous-entendu que l'on parle de sa version de décision. Sa version de décision est "Existe-t'il un chemin hamiltonien de poids <=k?"

On remarquera d’ailleurs dans ce cas particulier du problème de voyageur de commerce, que pouvoir résoudre le problème de décision en temps polynomial permet directement de résoudre le problème d'optimisation en temps polynomial. En utilisant la dichotomie afin d'obtenir le k optimal dans un premier temps (le plus petit pour lequel la réponse est oui). Puis en testant successivement, si en imposant de commencer le tour par (xixj), on augmente ou non le poids du tour optimal (ce qui permet de savoir si xixj fait partie d'un tour optimal,donc). Pour savoir si imposer de commencer le tour par (xixj) augmente le poids du tour optimal; il suffit de tester si, lorsque l'on modifie tous le poids (xixl) = ∞ pour tout l différent de j, alors il existe toujours un chemin hamiltonien de longueur k dans ce nouveau graphe. En faisant ça récursivement on peut calculer le tour optimal du problème de voyageur de commerce sur un graphe à N sommets en se posant un nombre polynomial de fois la question "Existe-t'il un chemin hamiltonien de poids <=k?" sur des graphes à N sommets.

--Pparent (discuter) 20 décembre 2013 à 00:46 (CET)

L'optimisation n'est PAS dans NP-Complet

cette phrase me dérange énormement: " Il est à noter qu'il s'agit alors d'un abus de langage de parler de problème NP pour certains de ces problèmes, car ils ne sont pas des problèmes de décision. Cependant, les problèmes de décision associés à un problème d'optimisation, typiquement de la forme : « telle solution est-elle optimale ? » ou « existe-t-il une solution de coût inférieur à... ? », sont eux bien NP-complets. "

Je suis bien d'accord que « existe-t-il une solution de coût inférieur à... ? » est un problème NP complet, mais « telle solution est-elle optimale ? » ne l'est pas. Elle sous entends de démontrer (entre autres) qu'il n'y a pas de solution meilleur, et ceci n'est pas si simple !!

Une correction, et un lien vers les pages NPO / coNP-complet semble bien plus correcte !!!!

Bonjour,

Alors « telle solution est-elle optimale ? » est un problème de décision qui est NP (et le plus souvent NP-Complet en fonction du problème) si le problème associé « existe-t-il une solution de coût inférieur à... ? » est NP-Complet. En effet ta question "telle solution est-elle optimale ?" revient à poser, si ta solution a un coût k, « existe-t-il une solution de coût inférieur ou égal à k-1 ? »

Le problème d'optimisation est quand à lui de la forme "Trouver une solution de coût optimal" ce qui n'est pas un problème de décision (dont la réponse est oui ou non) et ne peut donc pas être dans NP par définition. Par contre il est à noter que dans la plupart des cas la résolution d'un problème d'optimisation peut se réduire à la résolution d'un nombre polynomial du problème de décision associé, comme j'avais déjà dut l'expliquer dans un page de discussion sur un des article de la théorie de la complexité. (EDIT: juste au dessus en fait)

--Pparent (discuter) 4 novembre 2014 à 12:55 (CET)

Bonjour, je ne suis pas sûr d'avoir compris ta réponse. Il me semble que l'anonyme a raison : « telle solution est-elle optimale ? » est un problème de co-NP et non de NP a priori. Je suis partisan de ne laisser que « existe-t-il une solution de coût inférieur à... ? ».--Roll-Morton (discuter) 4 novembre 2014 à 14:40 (CET)

Je fais le retrait, jusqu'à ce cette conversation reprenne.--Roll-Morton (discuter) 17 novembre 2014 à 20:47 (CET)

Ok pour la suppression. Mais le problème « telle solution X est-elle optimale ? » (PB1) est bien NP si « existe-t-il une solution de coût inférieur à... ? » (PB2) est NP-Complet. Preuve: tout instance de PB1 se ramène en temps polynomiale à la résolution d'un instance PB2. Algo de réduction de PB1 à PB2: 1- calculer le coût k de la solution X . 2- résoudre le problème « existe-t-il une solution de coût inférieur à k ? » (Si la réponse est oui X n'est pas optimal, sinon X est optimal).--Pparent (discuter) 18 novembre 2014 à 11:12 (CET)

Il me semble que ta preuve ne va pas dans le bon sens. Pour montrer qu'un problème est NP-complet, on doit montrer :

• qu'il est dans NP, ie qu'il existe un certificat vérifiable en temps polynomial, ce qui ne me semble pas évident ici (comment montrer qu'une solution est optimale sans faire la liste de toutes les solutions ?)
• qu'il est au moins aussi dur qu'un problème NP-complet : par exemple avec tes notations, étant donné une instance de PB2 je peux la résoudre en utilisant un algo pour PB1 plus un algo en temps polynomial (c'est à dire le sens inverse de ta preuve je crois).

Ces trucs de NP/coNP sont toujours déroutants donc je peux me tromper, mais je crois que c'est juste.--Roll-Morton (discuter) 18 novembre 2014 à 10:35 (CET)

Donc si tu préfères si on a un algorithme A2 qui permet de vérifier un certificat pour (PB2) en temps polynomial, car PB2 est NP-Complet. Alors pour tout instance de PB1 il existe une instance de PB2 associée comme montrée au dessus. Si la réponse est oui à l'instance (de PB1 et PB2) alors il existe un certificat pour PB2 qui sera vérifié en temps polynomial par A2, Et il existe ce même certificat pour l'instance correspondante de PB1 qui sera vérifié par l'algo A1 (polynomial): "Transformer l'instance en instance de PB2 et vérifier que le certificat est valide pour cette instance de PB2 via A2".--Pparent (discuter) 18 novembre 2014 à 11:12 (CET)

Ps: je n'ai pas dit pour l'instant qu'il est nécessairement NP-Complet, mais au moins NP. --Pparent (discuter) 18 novembre 2014 à 11:15 (CET)

Je crois qu'il y a encore un problème : un certificat pour le PB1 est quelque chose qui montre que la réponse est "oui", par exemple une solution de coût inférieur à k. Il n'y a pas, a priori, de certificat qui montre que la réponse est non, ie je ne peux pas te donner quelque chose qui te montre directement qu'il n'y a pas de solution de coût inférieur à k. Ce que je veux dire est que fondamentalement tu cherches à faire un lien entre "non" à PB1 et "oui" à PB2, et ça ne marche pas puisque l'appartenance à NP ne t'assure que de l'existence d'un certificat "oui" que pour les mots du langage. --Roll-Morton (discuter) 18 novembre 2014 à 12:38 (CET)

Ha oui ok je vois ce que tu veux dire, le problème PB1 est Co-NP. Effectivement il faudrait associer plutôt le problème "Est-ce qu'il existe une solution meilleur que X?", ou bien "Est-ce que X est sous-optimale", qui lui est NP.--Pparent (discuter) 20 novembre 2014 à 09:56 (CET)

Désolé de ne pas avoir répondu avant. Oui, je crois qu'on est sur la même longueur d'onde maintenant.--Roll-Morton (discuter) 10 décembre 2014 à 15:59 (CET)

Diagramme d'Euler des problèmes NP

 Cbyd : L'idée d'une illustration des problèmes NP-complets par un digramme de Venn (ou d'Euler) est une bonne idée, mais je mettrais un gros point d'interrogation dans la partie intermédiaire ente P et NP. --Pierre de Lyon (discuter) 8 août 2018 à 09:04 (CEST)

Bonjour PIerre.Lescanne (d · c · b). Pour modifier un tel diagramme, il faudrait s'adresser à l'atelier des graphistes, qui pourraient au passage franciser si on leur fournit les textes ; je vais voir si je peux bricoler un graphique moi-même, ne serait-ce que pour fournir à l'atelier les bonnes spécifications.--Cbyd (discuter) 8 août 2018 à 10:41 (CEST)

Définition Formelle

Si le langage donné est l'ensemble des mots pour lesquels la réponse est oui, comme il est écrit dans le texte, un algorithme donne la solution en temps constant: il suffit de dire oui.

Il me semble que le langage en question est l'ensemble des mots décrivant toutes les instances du problème. La machine doit alors décider si, pour un mot donné (une instance donnée) la réponse est oui. Je me trompe ?--JC.Raoult (discuter) 10 janvier 2022 à 12:45 (CET)

Euh, oui, en effet, vous vous trompez, mais il faut bien reconnaitre que pour le profane, la rédaction de notre article n'est absolument pas claire. On part d'un alphabet A, et de l'ensemble M des mots formés avec A (des suites de symboles de A). Un langage formel est un sous-ensemble L de M, et le problème de décision correspondant est de savoir si un mot donné de M appartient à L. Cordialement,--Dfeldmann (discuter) 10 janvier 2022 à 13:06 (CET)