«Où sont les problèmes vraiment difficiles»? Quelles sont les idées actuelles sur le sujet?

J'ai trouvé ce document très intéressant. Pour résumer: il explique pourquoi, dans la pratique, vous trouvez rarement le pire cas d'un problème NP-complet. L'idée de l'article est que les instances sont généralement très sous ou très contraignantes, les deux étant relativement faciles à résoudre. Il propose ensuite pour quelques problèmes une mesure de «contrainte». Ces problèmes semblent avoir une «transition de phase» de 0 probabilité de solution à 100% de probabilité. Il émet alors l'hypothèse:

1. Que tous les problèmes NP-complets (ou même tous les problèmes NP) ont une mesure de «contrainte».
2. Que pour chaque problème NP-complet, vous pouvez créer un graphe de la probabilité d'une solution existante en fonction de la «contrainte». De plus, ce graphique contiendra une transition de phase où cette probabilité augmente rapidement et considérablement.
3. Les exemples les plus défavorables des problèmes NP-complets résident dans cette transition de phase.
4. Le fait qu'un problème repose sur cette transition de phase reste invariant lors de la transformation d'un problème NP-complet en un autre.

Ce document a été publié en 1991. Ma question est la suivante: y a-t-il eu des recherches de suivi sur ces idées au cours des 25 dernières années? Et si oui, quelle est la pensée dominante actuelle à leur sujet? Ont-ils été trouvés corrects, incorrects, non pertinents?

Voici un résumé approximatif de l'état basé sur une présentation donnée par Vardi lors d'un atelier sur la théorie des modèles finis et algorithmiques (2012):

Il a été observé que les instances dures se situent à la transition de phase d'une région sous-contrainte à une région trop contrainte. La conjecture fondamentale est qu'il existe un lien étroit entre les transitions de phase et la complexité de calcul des problèmes NP.

$P \ne NP$$P$

La pensée dominante actuelle semble être (comme l'a déclaré Vardi) que les transitions de phase ne sont pas intrinsèquement liées à la complexité informatique.

Enfin, voici un article publié dans Nature qui étudie le lien entre les transitions de phase et la dureté de calcul de K-SAT.

Oui, il y a eu beaucoup de travail depuis l'article de Cheeseman, Kanefsky et Taylor de 1991.

La recherche d'examens des transitions de phase des problèmes NP-Complete vous donnera de nombreux résultats. Un tel examen est Hartmann et Weigt [1]. Pour une introduction de niveau supérieur, voir les articles de Brian Hayes American Scientist [2] [3].

L'article de Cheesemen, Kanefsky et Taylor de 1991 est un cas malheureux d'informaticiens qui ne prêtent pas attention à la littérature mathématique. Dans l'article de Cheeseman, Kanefsky et Taylor, ils ont identifié le cycle hamiltonien comme ayant une transition de phase avec une augmentation des coûts de recherche près du seuil critique. Le modèle de graphique aléatoire qu'ils ont utilisé était un graphique aléatoire d'Erdos-Renyi (probabilité de bord fixe ou distribution équivalente de degrés gaussiens). Ce cas a été bien étudié avant l'article de Cheeseman et all de 1991 avec des algorithmes de temps polynomiaux presque sûrs connus pour cette classe de graphique, même au seuil critique ou près de celui-ci. Les "Graphes aléatoires" [4] de Bollobas sont une bonne référence. La preuve originale, je crois, a été présentée par Angliun et Valiant [5] avec des améliorations supplémentaires par Bollobas, Fenner et Frieze [6]. Après Cheeseman,

La transition de phase pour les cycles hamiltoniens dans les graphiques aléatoires Erdos-Renyi aléatoires existe en ce sens qu'il y a une transition rapide de la probabilité de trouver une solution, mais cela ne se traduit pas par une augmentation de la complexité "intrinsèque" de la recherche de cycles hamiltoniens. Il existe des algorithmes de temps polynomiaux presque sûrs pour trouver des cycles hamiltoniens dans les graphes aléatoires d'Erdos-Renyi, même à la transition critique, à la fois en théorie et en pratique.

La propagation de l'enquête [8] a réussi à trouver des instances satisfaisantes pour le 3-SAT aléatoire très près du seuil critique. Mes connaissances actuelles sont un peu rouillées, donc je ne sais pas s'il y a eu de gros progrès dans la recherche d'algorithmes "efficaces" pour les cas non satisfaisants près du seuil critique. 3-SAT, pour autant que je sache, est l'un des cas où il est "facile" de résoudre s'il est satisfaisable et proche du seuil critique mais inconnu (ou difficile?) Dans le cas non satisfaisant près du seuil critique.

Mes connaissances sont un peu dépassées, mais la dernière fois que j'ai examiné ce sujet en profondeur, il y a eu quelques points qui m'ont frappé:

• Le cycle hamiltonien est "facile" pour les graphes aléatoires d'Erdos-Renyi. Où sont les problèmes difficiles pour cela?
• La partition numérique devrait être résoluble très loin dans la région de probabilité presque sûre 0 ou 1, mais aucun algorithme efficace (à ma connaissance) n'existe pour des tailles d'instance même modérées (1000 nombres de 500 bits chacun est, pour autant que je sache, complètement intraitable avec algorithmes de pointe). [9] [10]
• 3-SAT est "facile" pour les instances satisfaisables proches du seuil critique, même pour des tailles d'instances énormes (millions de variables) mais difficile pour les instances non satisfaisantes proches du seuil critique.

J'hésite à l'inclure ici car je n'en ai pas publié d'articles, mais j'ai rédigé ma thèsesur le sujet. L'idée principale est qu'une classe possible d'ensembles aléatoires (cycles hamiltoniens, problème de partition numérique, etc.) qui sont «intrinsèquement difficiles» sont ceux qui ont une propriété «d'invariance d'échelle». Les distributions stables de Levy sont l'une des distributions les plus naturelles avec cette qualité, ayant des queues de loi de puissance, et on peut choisir des instances aléatoires parmi des ensembles NP-Complete qui incorporent d'une manière ou d'une autre la distribution stable de Levy. J'ai donné quelques preuves faibles que des instances intrinsèquement difficiles du cycle hamiltonien peuvent être trouvées si des graphiques aléatoires sont choisis avec une distribution de degré stable à Levy au lieu d'une distribution normale (c'est-à-dire Erdos-Renyi). À tout le moins, cela vous donnera au moins un point de départ pour une revue de la littérature.

[1] AK Hartmann et M. Weigt. Transitions de phase dans les problèmes d'optimisation combinatoire: principes de base, algorithmes et mécanique statistique. Wiley-VCH, 2005.

[2] B. Hayes. Le problème difficile le plus simple. Scientifique américain, 90 (2), 2002.

[3] B. Hayes. Sur le seuil. Scientifique américain, 91 (1), 2003.

[4] B. Bollobás. Graphes aléatoires, deuxième édition. Cambridge University Press, New York, 2001.

[5] D. Angluin et LG Valiant. Algorithmes probabilistes rapides pour circuits et appariements de Hamilton. J. Computer, Syst. Sci., 18: 155-193, 1979.

[6] B. Bollobás, TI Fenner et AM Frieze. Un algorithme pour trouver des chemins et des cycles de Hamilton dans des graphiques aléatoires. Combinatorica, 7: 327–341, 1987.

[7] B. Vandegriend et J. Culberson. La transition de phase G n, m n'est pas difficile pour le problème du cycle hamiltonien. J. of AI Research, 9: 219–245, 1998.

[8] A. Braunstein, M. Mézard et R. Zecchina. Propagation de l'enquête: un algorithme de satisfiabilité. Random Structures and Algorithms, 27: 201–226, 2005.

[9] I. Gent et T. Walsh. Analyse de l'heuristique pour le partitionnement des nombres. Computational Intelligence, 14: 430–451, 1998.

[10] CP Schnorr et M. Euchner. Réduction de la base du réseau: algorithmes pratiques améliorés et résolution des problèmes de somme des sous-ensembles. Dans Proceedings of Fundamentals of Computation Theory '91, L. Budach, éd., Lecture Notes in Computer Science, volume 529, pages 68–85, 1991.

25 ans d'études, et où sont les idées actuelles:

+++ idée 1:

Dans mon expérience de la résolution de satisfiabilité, j'ai trouvé dans la pratique que l'ajout d'une clause k valide à une formule que nous essayons de résoudre est similaire à la décision d'une variable (nk) qbf.

Cela semblerait être une approche pour montrer que les méthodes actuelles de résolution sat pour NP sont très difficiles!

+++ idée 2:

Une autre idée est que le problème AllQBFs est un vrai problème dans la hiérarchie booléenne. Le problème AllQBFs est: Produire une expression booléenne Q qui décide tous les 2 ^ n qbfs d'une formule R. AllQBFs est facile lorsque la formule originale R est monotone ou 2-cnf.

AllQBFs semble être une voie plausible pour montrer que QBF est Exp, car Q est souvent exponentiel, donc l'évaluation d'une affectation de Q (une quantification de la formule originale R) est exponentielle. Donc, la route pour prouver NP est Exp, au moins quelques briques.

+++ idée 3: k-cnfs réguliers

Btw, toutes les études de transition de phase ont manqué les k-cnfs réguliers, où le nombre d'occurrences d'une variable (dans les deux sens) est fixe, similaire aux graphiques réguliers en degrés ... Les k-cnfs réguliers deviennent beaucoup plus difficiles que le modèle standard, parce que toutes les variables semblent identiques en termes de contraintes sur elles.

Il y a vingt-cinq ans, juste après avoir lu cheeseman, je me suis concentré sur la coloration régulière des graphiques en degrés, car toutes les variables se ressemblent. Je vais donc abuser de mon privilège de réponse ici, et présenter vingt-cinq ans de résultats sur des graphiques réguliers!

+++ idée 4: Golden Points pour les études de référence de satisfiabilité

J'ai beaucoup étudié la coloration C des graphes D des sommets N réguliers. Le tableau suivant résume les résultats Golden Point pour la coloration régulière des graphiques.

Pour une probabilité élevée, N instances aléatoires étaient satisfaisables. Pour Très élevé, N ^ 2 étaient satisfaisables. Pour Super High, N ^ 3 instances aléatoires étaient satisfaisables.

Les points de coloration dorée à haute probabilité (1 - 1 / N) sont:

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Les points de coloration dorée à très haute probabilité (1 - 1 / (N ^ 2)) sont:

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Les points de coloration dorés à très haute probabilité (1 - 1 / (N ^ 3)) sont:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

L'entrée C4D9 indique quatre couleurs de graphiques du neuvième degré. Ce sont les 4cnfs aléatoires les plus difficiles que j'ai rencontrés en 25 ans de résolution sat. J'ai récemment coloré un graphique de 172 sommets au neuvième degré après dix jours de temps processeur.

+++ Idée 5: Le C5D16N ???? Golden Point est légèrement conjecturé pour exister.

Merci, Daniel Pehoushek