Quelle est la fréquence de transition de phase dans les problèmes NP-complets?

Il est bien connu que de nombreux problèmes NP-complets présentent une transition de phase. Je m'intéresse ici à la transition de phase par rapport au confinement dans le langage, plutôt qu'à la dureté de l'entrée, par rapport à un algorithme.

Pour rendre le concept sans ambiguïté, définissons-le formellement comme suit. Une langue $L$ présente une transition de phase (par rapport au confinement), si

1. Il existe un paramètre d'ordre $r(x)$ , qui est une fonction polynomiale calculable en temps réel de l'instance.

2. Il y a un seuil $t$ . C'est soit une constante réelle, soit elle peut dépendre de $n=|x|$, c'est-à-dire $t=t(n)$ .

3. Pour presque tous les $x$ avec $r(x)<t$ , nous avons $x\in L$ . ( Presque tous les moyens ici: presque tous disparaissent, c'est-à-dire que la proportion approche 1, comme $n\rightarrow\infty$ ).

4. Pour presque tous avec , nous avons .r ( x ) > t x ∉ $x$$r(x)>t$$x\notin L$

5. Pour presque tous les , il considère que . (C'est-à-dire que la région de transition est "étroite".)r ( x ) ≠ $x$$r(x)\neq t$

De nombreux problèmes naturels NP-complets présentent une transition de phase dans ce sens. Les exemples sont de nombreuses variantes de SAT, toutes les propriétés de graphes monotones, divers problèmes de satisfaction des contraintes, et probablement beaucoup d'autres.

Question: Quelles sont les "belles" exceptions? Existe-t-il un problème naturel NP-complet, qui (probablement) n'a pas de transition de phase dans le sens ci-dessus?

des chercheurs experts dans ce domaine affirment essentiellement que les transitions de phase sont une caractéristique universelle des problèmes complets de NP, bien que cela n'ait pas encore été formulé / prouvé rigoureusement et qu'il ne soit pas encore largement considéré / diffusé dans le domaine plus large (il émane davantage d'une approche empirique). branche d'étude). sa conjecture presque ouverte. il existe des preuves solides. il n'y a pas de candidats plausibles pour les problèmes complets de NP sans transition de phase. voici deux refs qui supportent ce pov:

• Transitions de phase dans les problèmes NP-complets: un défi pour la probabilité, la combinatoire et l'informatique / Moore

• Comportement de transition de phase / Walsh (ppt)

voici un aperçu approximatif de la vérité de l'affirmation. cela concerne le P contenu dans NP complete. un problème / langage NP complet doit avoir des instances qui sont résolubles en temps P et d'autres qui peuvent être résolues en temps exponentiel (ou au moins superpolynomial) si P ≠ NP. mais il doit toujours y avoir un moyen de "grouper" les instances P des instances "non-P". par conséquent, il doit également toujours y avoir des "critères de transition" entre les instances P et non-P. en bref, peut-être que ce phénomène est intrinsèquement couplé avec P ≠ NP!

un autre argument grossier: tous les problèmes NP complets sont interchangeables via des réductions. si une transition de phase est trouvée dans une seule, elle doit être trouvée dans chacune d'elles.

une preuve plus circonstancielle de cela, plus récemment (~ 2010), il a été montré que la transition de phase apparaît pour les limites inférieures sur les circuits monotones pour la détection de clique sur des graphiques aléatoires.

• Complexité moyenne des cas de détection de cliques / Rossman

divulgation complète: Moshe Vardi a étudié les transitions de phase en particulier en SAT et a une vue contrastée plus sceptique dans cette conférence / vidéo.

• Transitions de phase et complexité de calcul

$G_{n,m}$$n$$m$$\binom{n}{2}$$m$$G_{n,m}$

La coloration C des graphes réguliers D a une série de transitions discrètes, pas particulièrement échelonnées, sauf si vous vous étirez.

Voici un tableau des résultats de coloration que je soumettrai à SAT17. Notez que 3 coloriages de 6 graphiques réguliers sont impossibles à l'exception de quelques exemples. De même 4 coloration des graphes au dixième degré ... Les graphes C3D5N180 sont légèrement difficiles. Le C4D9 Golden Point n'est que provisoirement à C4D9N180; Les graphiques C4D9 sont les 4cnfs les plus difficiles en taille que j'ai rencontrés, donc C4D9 est considéré comme un "point dur". Le point d'or C5D16 est supposé exister, mais se situerait dans la région du point dur de 5 à 6 couleurs.

          Universal Constants of Regular Graph Coloring

Les formules de coloration ont des variables lgC par sommet, pour un total de lgC * N variables; les bords ont des clauses de coloration C, pour un total de clauses C * M. Il y a quelques clauses supplémentaires par sommet pour exclure des couleurs supplémentaires. Les Golden Points sont les plus petits N tels que: La colorabilité C sur les graphiques de degré D avec N sommets est presque toujours satisfaisable, avec une probabilité proche de 1. Pour une probabilité élevée, N instances aléatoires étaient satisfaisables. Pour Very High, N * N étaient satisfaisables. Pour Super High, N * N * N 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 * N)) sont:

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

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

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

Tous les cas aléatoires de l'étude étaient satisfaisables. Les points de probabilité linéaires ont vérifié des centaines de formules satisfaisables. Les points de probabilité quadratiques vérifiaient des dizaines de milliers de formules satisfaisables. Les points de probabilité cubiques ont vérifié des centaines de milliers de formules satisfaisables. Les points C4D9 et C5D13 sont difficiles. Le point C5D16 est supposé exister. Une instance aléatoire de cinq colorables au seizième degré prouverait la conjecture.