Complexité des problèmes NP-complets

Bibix

Bonjour
J'ai découvert récemment qu'un problème d'optimisation pour lequel j'ai développé un algorithme de résolution exacte avait été démontré NP-complet (enfin, c'est évidemment le problème de décision associé qui l'est). Après calcul, j'ai obtenu une complexité en $O(T^{0.722 \ln(T)})$ où $T$ est la taille de l'input pour cet algorithme. Du coup, je me pose la question : peut-on construire avec ça un algorithme qui résoudrait exactement le problème du voyageur de commerce par exemple avec la même complexité ?

Ce serait bien meilleur que toutes les solutions exactes utilisées à ce jour il me semble. Mais j'ai aussi l'impression qu'il y a un loup car cet algorithme n'a rien de révolutionnaire, je mettrais ma main à couper que ça a déjà été trouvé.

Poirot

Il me semble que la définition d'un problème NP-complet signifie que tout problème NP peut être résolu avec un complexité polynomiale en la complexité de ton problème. Donc on obtiendrait quelque chose de polynomial en $T^{0,722 \ln(T)}$ pour le voyageur du commerce. Je ne saurais pas dire si c'est mieux que ce qui est connu là-dessus.

Heuristique

Bonjour @Bibix ,

Je t'invite à te méfier violemment des algorithmes de résolution exacte de problème $NP$-difficiles. Souvent, il y a une exponentielle cachée là où on ne s'y attend pas. Par exemple, on peut donner l'impression de résoudre le problème SOMME avec de la programmation dynamique en temps $O(s)$ (étant donné $A \subset \mathbb{N}$ et $s \in \mathbb{N}$, existe-t-il $I \subset A$ tel que $s = \sum\limits_{a \in I} a$ ). L'exponentielle est alors cachée dans le fait que les entiers sont représentés en binaire donc $s$ prend en entrée une taille en $O(ln(s))$. Utiliser $O(s)$ opérations est donc un algo exponentiel. N'as-tu pas fait ce genre d'erreur dans ton calcul de complexité ? A priori, les algos en $O(n^{ln(n)})$ ne tiennent pas longtemps avant de tomber dans $P$, je serais donc très étonné qu'on puisse faire du $O(n^{ln(n)})$ pour un problème $NP$-dur.

@Poirot Désolé mais ce n'est pas ça. Définition : un problème de décision est $NP$-complet s'il est dans $NP$ et si tout problème $NP$ se réduit à lui. En revanche, s'il existe un algo polynomial pour un problème $NP$-complet, on peut effectivement en déduire que tout problème $NP$ peut s'effectuer en temps polynomial. Toutefois, cela ne veut absolument pas dire que la complexité de tes algos seront celle du premier.

Poirot

La page Wikipedia sur les problèmes NP-complets dit que ton "se réduit à lui" signifie que pour tout problème NP, il existe une réduction polynomiale à notre problème. Cela ne se traduit pas par ce que j'ai dit ?

Bibix

L'entrée de mon algorithme, c'est $N$ points de $[0,1]^d$ et donc numériquement, si je code ça avec des flottants en $B$ bits avec $B$ suffisamment grand, ça donne $B N d \geq N d$ bits en entrée, non ?

Ensuite, mon algorithme calcule la solution optimale en $O(N^{\log_2(d)+1})$ si $d \geq 3$ (si $d < 3$, la complexité est polynomiale) ce qui donne bien ce que j'ai mis dans mon message... mais je suis du même avis, je n'ai jamais entendu parler que les problèmes NP avaient tous potentiellement une complexité en $O(n^{k \ln(n)})$ avec $k$ fixé. Je ne connaissais que les algos en $O(n^{k \sqrt{n}})$ avec les plans séquants qui sont beaucoup utilisés en optimisation combinatoire...

Heuristique

@Poirot Non, tu peux juste assurer temps polynomial car il faut compter la complexité de la réduction. Un exemple : HORNSAT est un problème $P$-complet, c'est-à-dire que tout problème de $P$ se réduit en espace logarithmique à HORNSAT. De plus, HORNSAT est un problème qui se résout en temps linéaire. Cela ne signifie pas pour autant que tous les problèmes de $P$ peuvent se résoudre en temps linéaire, car la réduction à HORNSAT peut coûter un temps quadratique par exemple. La raison pour laquelle on considère les classes $P$ ou $NP$ et pas une classe $Quad$ des problèmes qui se résolvent en temps quadratique est que cette dernière n'est close par aucune réduction (ce qui est le cas de $P$ et $NP$).

@Bibix Ton problème précise explicitement que les flottants sont codés sur $B$ bits ? En général, ce sont les entiers ou les rationnels qui créent des problèmes e combinatoire $NP$-durs et passer en réel simplifie grandement le problème.

Bibix

L'article qui en parle l'avait défini pour des points dans $\mathbb{R}^d$ mais pour démontrer la NP-complétude, les auteurs utilisent une réduction au problème de l'ensemble indépendant maximal et en fait, il suffit de prendre $\{0,1\}^{|V|}$ pour un ensemble $V$ de nœuds dans le graphe dans la preuve donc il semblerait même que $B=1$ suffise. Après avoir lu l'article en détail, je remarque que les auteurs utilisent le même genre d'algorithme naïf que moi mais ils n'ont pas pensé à mentionner la complexité de leur algorithme ce qui est suspect. Peut-être que c'est une vaste blague de la part de ces chercheurs ? L'article date de 20 ans quand même, alors que c'est potentiellement une avancée majeure.

Je n'ai absolument pas le temps de m'en occuper en ce moment mais peut-être qu'on peut effectivement creuser pour rendre l'algo polynomial et prouver ce satané $P = N P$...

En tout cas, merci @Poirot et @Heuristique, au moins pour la confirmation de l'intérêt potentiel du truc.

denise chemla

Bonsoir,

Je vous conseille une référence (mais peut-être la connaissez-vous) : c'est le livre de Garey et Johnson : dans mes souvenirs, il y avait plein de preuves de "passages" d'un problème NP à un autre ; il s'agissait de trouver à chaque fois la bonne bijection, qui rendait les 2 problèmes de complexité identique, ou calculable l'une en fonction de l'autre. J'espère ne pas me tromper de livre car ma lecture date (1987).
Cordialement,
Denise Vella-Chemla