Cette question est étroitement liée à un autre article: Transitions de phase dans les problèmes difficiles NP, mais elle est quelque peu différente. Bien que cette question concerne la dureté d'instances particulières de problèmes difficiles NP, il s'agit de classer la difficulté des mêmes instances.
Il y a beaucoup de bibliographie sur l'effet connu sous le nom de transition de phase . En particulier pour le cas des formules aléatoires 3-SAT sous forme normale conjonctive (CNF), il est connu qu'il existe une valeur R du rapport des clauses aux variables de sorte que pour tout r <R la formule peut être satisfaite avec une probabilité élevée et pour r> R, la formule est insatisfaisante avec une probabilité élevée. L'effet de transition de phase se produit près de R et il a pour effet remarquable que la résolution du problème de satisfiabilité pour ces formules est extrêmement difficile en pratique.
Étant donné que pour prouver la dureté NP d'un problème donné, il est nécessaire de montrer qu'il existe un temps polynomial de réduction de Turing d'un problème NP-complet et que les problèmes qui sont NP-complets peuvent être transformés en temps polynomial parmi eux, alors le la question suivante se pose naturellement:
Est-il possible de classer la difficulté des problèmes difficiles de NP dans la pratique en utilisant la transition de phase du CNF 3-SAT comme indicateur? L'intuition est qu'un problème P1 devrait être plus difficile que P2 si son codage 3-SAT est plus proche de R (qui est connu pour être proche de 4,2). Notez que cette idée ne lie pas nécessairement chaque instance particulière à une difficulté particulière, elle les classe simplement.
Il existe un certain nombre de contre-arguments, parmi eux:
- La transition de phase de la formule CNF 3-SAT s'applique aux formules aléatoires. Cependant, une instance particulière dans un problème différent a une structure qui pourrait être exploitée par les résolveurs pour ce problème --- cela a déjà été souligné par Peter Shor dans la question susmentionnée.
- Il se peut que l'encodage particulier utilisé pour transformer les instances particulières de notre problème en 3-SAT joue un rôle crucial dans le rapport des clauses aux variables conduisant à des valeurs trompeuses, d'où des erreurs de classification --- cette préoccupation est soulevée par Kaveh dans les commentaires sur cette question.
- Serge (d'après ce que j'ai compris de son commentaire à cette question) soulève la question que l'on pourrait compliquer artificiellement le problème dur NP d'origine afin qu'il en résulte une formule 3CNF qui modifie le rapport des clauses aux variables tout en préservant la satisfiabilité.
Comme pour 1, tous les problèmes peuvent partager la même classe de régularité afin que les problèmes de classement (au lieu de caractériser la difficulté) puissent s'appliquer; comme pour 2, il existe des codages dans des problèmes particuliers qui sont connus pour être non redondants par rapport à la règle de propagation d'unité de sorte que ceux-ci devraient être préférés et peut-être qu'ils évitent ces erreurs de classification. Un exemple est Sideris et al., 2010 pour le cas de la planification propositionnelle. Quant à 3, Cheeseman et al., 1991 a déjà examiné la question de savoir si les correspondances entre les problèmes préservent ou non l'effet de transition de phase et leurs expériences préliminaires semblent soutenir leur conjecture, à condition que l'on réduise le problème NP initial et même que " peut être encore réduit en appliquant une résolution aux clauses ".
Est-ce que tout cela a du sens pour vous? connaissez-vous des références bibliographiques à ce sujet? Toute orientation serait largement reconnue!
la source
Réponses:
Bien qu'il ne soit pas inconcevable que les obstacles techniques que vous mentionnez puissent être surmontés d'une manière ou d'une autre, je pense qu'il y a actuellement très peu de motivation pour le faire, pour la simple raison que (du moins pour autant que je sache) la difficulté de NP-hard les problèmes dans la pratique semblent, empiriquement, avoir peu à voir avec leur proximité avec la transition de phase 3-SAT.
Comparez cela à d'autres façons de classer les problèmes NP-difficiles en termes de difficulté: il existe une corrélation empirique entre les problèmes NP-difficiles qui sont faciles en pratique et les problèmes NP difficiles qui sont faciles à estimer ou qui sont traitables à paramètres fixes. (au sens de complexité paramétrée). Des notions appropriées de réduction ont été développées dans ces cas qui expliquent en partie les observations empiriques. Cependant, il ne semble actuellement pas y avoir d'indication empirique que la plupart des problèmes NP-difficiles qui sont difficiles dans la pratique sont difficiles en raison de leur relation étroite avec les instances 3-SAT près de la transition de phase. Il n'est donc pas très logique d'élaborer une théorie pour «expliquer» quelque chose qui ne semble pas être vrai dans la pratique.
la source