Dr Pyviv@tanavit en fait, les problèmes sont démontrés comme étant équivalent : on peut utiliser la solution de l'un pour en résoudre un autre. En gros, on peut coder la division des grands nombres avec des flips de triangulations
Tom@pyviv @tanavit Et puis la complexité est un zoo ! Ici on parle de complexité "au pire", donc on prend en compte ce qui se passe pour les polygones les plus difficiles ! Mais une méthode peut néanmoins bien marcher quasiment tout le temps (exemple de l'algorithme du simplexe) et mal se comporter uniquement sur des exemples pathologiques qui ne se rencontrent pas en pratique. Il y a d'autres notions de complexités (en moyenne, lissée ...) qui visent à capturer ça, qui peuvent donner une vision différente de la difficulté d'un pb.
Le Néandertal se sent las, las@thoasm @pyviv @tanavit donc pour certains ou même la plupart des problèmes NP complets il y a des méthodes qui marchent "bien" sur des exemples "typiques" (les mots entre guillemets sont à définir et on imagine qu'il y a plusieurs façons rigoureuses de le faire). De plus tous les problèmes NP complets se réduisent les uns aux autres.
Est-ce qu'après réduction, disons, du problème du voyageur du commerce à SAT, les exemples typiques de problème de voyageur commerce produisent des exemples typiques de SAT ? (Et vive versa œuf corse).
Et est-ce qu'il y a une réduction de SAT vers le voyageur du commerce qui permet de retrouver le problème de départ, ou on se retrouve avec deux problèmes de voyageurs du commerce équivalents de façon non triviale, le second sur un graphe beaucoup plus gros que le premier ?
Est-ce que ce genre de considération permet de hiérarchiser les problèmes NP complets ? Voire les méthodes de réduction ?
@HydrePrever @pyviv @tanavit
C'est de très bonne questions mais à ma connaissance (qui date un peu beaucoup) c'est des trucs qu'on sait pas trop faire.
Il y a pas mal de problèmes pour lesquels on peut classer des sous-classes en plus faciles si elles ont telles ou telle structures. Il y a des travaux statistiques sur la structures des problèmes particuliers pour déterminer ce qui le rend difficile, par exemple pour SAT et des instances aléatoires https://cgi.cse.unsw.edu.au/~tw/gwki94.pdf (sachant que les instances pratiques sont rarement "aléatoires"), mais relativiser tout ça avec des réduction … j'ai pas connaissance (mais c'est que moi).
@HydrePrever @pyviv @tanavit
Et le seul requis pour les réduction est que la transformation soit polynomiale. Elle n'est généralement pas du tout "bijective", c'est une injection qui ne fonctionne généralement pas dans l'autre sens. Donc pas vraiment de garantie de préservation des structures en général, en tout cas trivialement.
Et le seul requis pour les réduction est que la transformation soit polynomiale. Elle n'est généralement pas du tout "bijective", c'est une injection qui ne fonctionne généralement pas dans l'autre sens. Donc pas vraiment de garantie de préservation des structures en général, en tout cas trivialement.