NP-complet et NP-difficile

[invite950f8518]

Bonjour,

j'ai beaucoup lu ici et là que le problème du voyageur de commerce (minimiser la longueur de cycle hamiltonien) est NP-complet.

Bon, trouver un cycle hamiltonien dans un graphe quelconque est NP-complet (si le graphe n'est pas un cas facile, comme un graphe complet) : on peut tester si une solution donnée est valide en temps polynomial, et on peut ramener le problème 3-sat à ce problème en temps polynomial.

Mais le problème du voyageur de commerce (qui consiste à trouver le plus court cycle hamiltonien), je ne vois pas pourquoi il est NP-complet. D'abord, je ne vois pas comment tester si une solution donnée convient en temps polynomial (comment tester, en temps polynomial, si un cycle donné est bien le plus court de tous les cycles hamiltoniens).
En fait, même si on possédait une boîte noire nous permettant de trouver des cycles hamiltoniens dans un graphe quelconque en temps polynomial (P=NP), je ne vois pas comment résoudre le problème du voyageur de commerce en temps polynomial...

Ma question : le problème du voyageur de commerce ne ferait-il pas partie d'une classe plus "difficile" de problème, comme la classe "NP-difficile" (et ne serait absolument pas NP-complet, dans le sens où le fait de prouver P=NP ne permettrait pas de trouver un algorithme polynomial pour résoudre le voyageur de commerce) ?

Merci pour votre aide.
-----

[acx01b]

salut,

NP-complet : appartient à NP et tous les problèmes NP peuvent se ramener à ce problème

tu peux montrer facilement qu'il existe un problème NP-complet (NP-difficile suffit) qui se ramène (se réduit) à TSP (voyageur de commerce) : par exemple le problème du cycle hamiltonien ... donc TSP est bien NP-difficile

après tu remets en doute que TSP soit bien dans NP ?

[acx01b]

alors je me suis rappelé d'un de mes cours :

on peut prouver que TSP "entier " est bien dans NP en considérant un sous-problème :

problème de décision TSP-L : dans un graphe G donné à poids entiers, existe-t-il un cycle hamiltonien de longueur inférieure ou égale à L

on a bien le critère du certificat : pouvoir vérifier facilement (temps polynomial) si un cycle hamiltonien a bien une longueur inférieure ou égale à L

ensuite comme tu peux résoudre TSP en appliquant au maximum K (= somme des poids des arrêtes du graphe) fois le sous problème TSP-L, on a bien que TSP (à poids entiers) est dans NP

on peut aller plus loin en disant que TSP-L peut être transformé "aisément" en un problème SAT, je te laisses trouver comment

on peut donc en faisant K transformations TSP-L => SAT avoir un SAT qui résoud TSP (toujours si on a des poids entiers sinon c'est plus embêtant) ...

[invitebe0cd90e]

Sauf erreur de ma part, les notions de NP et de NP-completude sont reservées aux problemes de decision, cad dont la reponse est oui/non.

On appelle NP difficile un probleme qui n'est pas forcement un probleme de decision, mais dont la resolution entraine la resolution de tout probleme NP.

Donc tu as raison, en tant que tel le TSP est NP-difficile, mais il n'est pas NP ni NP-complet. Pour reprendre les termes de acx01b, c'est evident que si tu sais resoudre TSP, alors tu sais resoudre TSP-L pour tout L (entier ou pas, du coup).

Apres, si les poids sont entiers, on peut effectivement resoudre TSP en resolvant un nombre fini de TSP-L mais TSP n'est pas NP pour autant, vraiment par definition de ces classes de complexité.

[A voir en vidéo sur Futura]

[acx01b]

salut jobherzt,

est-tu d'accord qu'on peut transformer TSP-l en un problème SAT ? (réduction polynomiale), on peut le faire par exemple en codant les bits des nombres utilisés pour les calculs dans des variables binaires

est-tu d'accord que TSP (entier) peut être vu comme plusieurs TSP-l fait à la suite ?

donc pour moi on peut réduire TSP à SAT => pourquoi ne serait-il pas dans NP (puisque finalement c'est un problème SAT spécial) ?

[invitebe0cd90e]

Salut,

Je suis d'accord avec ca, relis mon message

C'est juste une question de vocabulaire, un probleme NP c'est un probleme de decision. TSP n'est pas un probleme de decision, donc il n'est pas NP, point.

Ce qui n'empeche absolument pas que sous certaines conditions on puisse resoudre TSP avec un algorithme permettant de resoudre des problemes NP.

Autrement dit, je suis d'accord qu'intuitivement TSP et les differents TSP-L sont "aussi difficiles".

[erik]

un probleme NP c'est un probleme de decision. TSP n'est pas un probleme de decision

AMHA, TSP est un problème de décision : "avons nous trouvé le plus court chemin ?" oui/non.

Il est possible que je me m'éprenne sur ce que tu appelles un problème de décision ...

[invitebe0cd90e]

Non, il y a une nuance :

- quand tu dis "existe t il un chemin dont la longueur est inferieure a L ?", tu poses une question qui est propre au graphe lui meme, cad que la reponse est "globalement" oui (un tel chemin existe) ou "globalement" non (un tel chemin n'existe pas).

- quand tu dis "avons nous le chemin le plus court ?", tu as deja choisi un chemin, cad que la reponse va etre "oui" pour certain chemin, et "non" pour d'autre.

Donc le premier est bien un probleme de decision, il y a des données (le graphe) et une seule reponse qui est oui ou non. Le second n'est pas un probleme de decision (il n'y a pas une unique reponse oui/non) mais un probleme d'optimisation (minimiser la distance parcourue).

[inviteea95960a]

Non, il y a une nuance :

- quand tu dis "existe t il un chemin dont la longueur est inferieure a L ?", tu poses une question qui est propre au graphe lui meme, cad que la reponse est "globalement" oui (un tel chemin existe) ou "globalement" non (un tel chemin n'existe pas).

- quand tu dis "avons nous le chemin le plus court ?", tu as deja choisi un chemin, cad que la reponse va etre "oui" pour certain chemin, et "non" pour d'autre.

Donc le premier est bien un probleme de decision, il y a des données (le graphe) et une seule reponse qui est oui ou non. Le second n'est pas un probleme de decision (il n'y a pas une unique reponse oui/non) mais un probleme d'optimisation (minimiser la distance parcourue).

Si, dans le deuxième cas on attend bien une réponse unique: les données sont un graphe et un chemin dans ce graphe, et on attend en résultat une réponse oui/non à la question "Le chemin donné est-il un des chemins les plus courts dans le graphe ?" (j'ai mi "un des chemins les plus courts" car a priori il peut exister plusieurs chemins qui ont la même longueur), ou si tu préfère exprimer les choses avec des "il existe" cela est la même chose que de répondre à la question "existe-il un chemin plus court que celui donné".

Donc d'après ce que tu as l'air de considéré comme un problème de décision, le problème de la vérification d'un chemin trouvé par un oracle est bien un problème de décision. Bref, dans les deux cas il s'agit bien d'un problème de décision, mais les données ne sont pas les mêmes. Dans le premier cas la donnée est une graphe seul, dans le deuxième c'est un couple graphe/chemin (ou un graphe étiqueté par un chemin). Mais peut-être qu'il faudrait que tu précise ce que tu appelles exactement un problème de décision si tu n'es pas d'accord.

Ensuite, la classe de problème NP ne s'adresse ni plus ni moins aux problèmes de décision que les autres classes. En fait si on vas par là on est obligé de se poser la question de la logique utilisée pour réponse à la question "existe-t-il ...". Si on utilise la logique classique il a une différence car en logique classique on peut prouver l'existence de certaines choses tout en étant incapable de construire l'objet. Mais si on est en logique intuitionniste (ou constructive) on ne peut prouver l'existence d'objets que par leur construction. Dans ce ce cas le problème de l'existence d'un solution (problème de décision: oui ça existe/non ça n 'existe pas) est équivalent au problème de recherche d'un solution.

Pour ceux qui ne connaissent pas la différence entre les deux logiques, voilà un petit exemple qui montre la différence entre les deux:
Prenons un train dont la gare de départ est Paris en France et la gare d'arrivé est Berlin en Allemagne, le train ne traverse aucun autre pays que la France et l'Allemagne. Sur son trajet le train ne s'arrête que dans deux gares: Strasbourg en France et Utopia. La trajet du train est donc Paris -> Strasbourg -> Utopia -> Berlin.

Question: existe-il une gare sur le trajet du train qui est en France et dont l'arrêt suivant se trouve en Allemagne ?

En logique classique on répond "oui", ou plus exactement il existe un preuve de l'existence de cette gare:
* soit Utopia est en France et alors c'est une solution au problème puisque la gare suivante est Berlin qui n'est pas en France.
* Soit Utopia est en Allemagne (une gare sur le trajet de ce train est soit en France soit en Allemagne selon l'énoncé), et alors Strasbourg est une solution au problème puisque Strasbourg est en France et la gare suivante (Utopia) est en Allemagne.

Bref, voilà un exemple de cas en logique classique où on peut prouver l'existence de quelque chose sans qu'il soit possible de construire une solution au problème.

En logique intuitionniste la réponse serait qu'il n'existe pas de preuve de l'existence d'un solution, mais il n'existe pas de preuve non plus de la non existence de la solution. Cette propriété ferait alors partie (en supposant la consistance de la logique, ce qu'on ignore) des questions "sans réponses" qui rendent la logique incomplète (Rq: la logique classique aussi est incomplète, toujours en supposant qu'elle soit consistante).

Bref, c'est pour ça que je dis qu'il faudrait encore définir exactement que qu'on appelle un problème de décision car suivant le sens qu'on donne aux mots "vrai" et "faux" ce n'est pas la même chose.

Pour revenir à l'exemple avec le train: si on donne aux mots "vrai"/"faux" le sens de la logique classique, alors on a bien un algorithme qui peut répondre à la question "existe-il une gare sur le trajet du train qui est en France et dont l'arrêt suivant se trouve en Allemagne". En revanche il n'existe aucun algorithme qui donnera une solution au problème".

Si on donne au mot "vrai" ou au mot "faux" le sens de la logique intuitionniste (mais dans ce cas non n'avons pas "non(vrai)=faux" et "non(faux)=vrai") on peut donner un algorithme qui nous répondra vrai/non(vrai) ou faux/non(faux) mais pas un qui nous répondra obligatoirement vrai/faux (une troisième valeur pour "indéterminé sera nécessaire).

Dans l'exemple du train il nous manque en fait une information sur la position géographique d'Utopia et alors dans ce cas on serait capable de construire une solution.

Pour résumer: si on se place en logique classique, les problèmes de décision ne sont a priori pas équivalents aux problème de recherche de solution (même si dans beaucoup de cas ils peuvent l'être), alors qu'en logique intuitionniste les problème de décision sont équivalents aux problèmes de recherche de solution (puisqu'il est impossible de prouver l'existence d'une solution sans la construire). C'est pourquoi je disais qu'il faudrait préciser ce qu'on appelle un problème de décision.

Typiquement il n'est pas rare qu'en mathématiques la seule existence d'une solution suffise (quel que soit les hypothèses supplémentaires qu'on pourrait faire par la suite), alors qu'en informatique la seule existence ne nous suffit plus mais il nous faut souvent (mais peut-être pas toujours) savoir qu'il est possible de construire cette solution (même si on n'effectue pas nécessairement la construction en elle-même).

Dans le cas du voyageur de commerce, l'existence d'une solution est relativement évidente (il existe toujours un chemin dans le graphe - à moins d'avoir des culs de sac dans un graphe orienté ou un graphe non connexe, mais ce n'est pas le problème ici - et alors (1)soit il n'existe pas de chemin plus court et dans ce cas on a trouvé un chemin plus court, donc il en existe bien un, (2) soit il existe un chemin plus court que celui choisi et par récurrence on peut affirmer l'existence d'un chemin le plus court). Le problème "existe-t-il un chemin le plus court a donc un algorithme en temps constant (qui répond toujours "oui" sans réfléchir) si le graphe donné est supposé avoir les bonnes hypothèses du problème. Une question plus intéressante est donc de savoir si on est capable de construire cette solution: la réponse est évidemment oui puisqu'on a des algorithmes qui le font. En bref, la seule question intéressante est la complexité des algorithmes de construction d'une solution, pas des algo qui répondent que cette solution existe ou non.


Bref, je ne crois qu'on puisse se contenter de répondre: le problème initial n'est pas un problème de décision donc la question de savoir dans quelle classe de problème il se situe n'a pas de sens.

Je crois au contraire qu'en informatique on ne s'attache qu'à la construction des solutions, c'est-à-dire qu'on se place dans un cadre où tous les problèmes sont équivalents à un problème de décision, car on se place en fait le plus souvent dans le cadre de la logique intuitionniste.


Petite précision pour ceux qui ne connaissent pas: la logique intuitionniste c'est comme la logique classique sauf qu'on a enlevé l'axiome "A ou non A" (principe du tiers exclu" qui a par exemple comme conséquence que non(non(A)) n'est pas a priori équivalent à A, et on ne peut pas non plus a priori faire des raisonnement par cas (soit... soit...). Cela dit, on peut souvent prouvé "A ou non A" pour certains A précis et alors ces preuves suffisent à être capable de construire n'importe quel objet dont on a prouvé l'existence (en fait les preuves sont équivalentes à des algorithmes de construction). Cette logique n'est généralement pas utilisée en math car les mathématiciens aiment pouvoir prouver l'existence d'objets mathématiques en donnant un minimum d'hypothèses, et en particulier sans expliciter les hypothèses qui permettraien la construction de ces objets.