Exemples de transitions de phase de dureté

Supposons que nous ayons un problème paramétré par un paramètre de valeur réelle p qui soit "facile" à résoudre lorsque et "difficile" lorsque p = p 1 pour certaines valeurs p 0 , p 1 .$p=p_0$$p=p_1$$p_0$$p_1$

Un exemple est le comptage des configurations de spin sur les graphiques. En comptant les colorations appropriées pondérées, les ensembles indépendants, les sous-graphiques eulériens correspondent respectivement aux fonctions de partition des modèles hardcore, Potts et Ising, qui sont faciles à approximer pour "haute température" et difficiles à "basse température". Pour les MCMC simples, la transition de phase de dureté correspond à un point auquel le temps de mélange passe du polynôme à l'exponentiel ( Martineli, 2006 ).

Un autre exemple est l'inférence dans les modèles probabilistes. Nous «simplifions» un modèle donné en prenant combinaison 1 - p , p avec un modèle «toutes les variables sont indépendantes». Pour p = 1, le problème est trivial, pour p = 0, il est insoluble et le seuil de dureté se situe quelque part entre les deux. Pour la méthode d'inférence la plus populaire, le problème devient difficile lorsque la méthode ne parvient pas à converger, et le moment où il se produit correspond à la transition de phase (au sens physique) d'une certaine distribution de Gibbs ( Tatikonda, 2002 ).$1-p$$p$$p=1$$p=0$

Quels sont d'autres exemples intéressants du "saut" de dureté car certains paramètres continus varient?

Motivation: pour voir des exemples d'une autre "dimension" de dureté en plus du type de graphique ou du type logique

Dans l'approximation du pire cas standard, il existe de nombreux seuils précis lorsque le facteur d'approximation varie.

Par exemple, pour 3LIN, satisfaisant autant d'équations linéaires booléennes données sur 3 variables chacune, il existe un algorithme d'approximation d'assignation aléatoire simple pour l'approximation 1/2, mais toute approximation meilleure que certains t = 1/2 + o (1) est déjà aussi dur que SAT exact (conjecturé pour exiger un temps exponentiel).

Je ne sais pas exactement si c'est le type de problème que vous recherchiez, mais la transition de phase des problèmes NP-Complete est un phénomène (désormais) bien connu. Voir les articles de Brian Hayes "Can't Get No Satisfaction" sur la transition de phase 3-SAT et "The Easiest Hard Problem" sur la transition de la phase de partition numérique, pour des articles populaires sur le sujet.

Selman et Kirkpatrick ont été les premiers à montrer numériquement que la transition de phase pour le 3-SAT était lorsque le rapport des clauses aux variables était d'environ 4,3.

Gent et Walsh ont été les premiers à montrer numériquement que la transition de phase pour le problème de partition numérique s'est produite lorsque le rapport des bits à la longueur de la liste était d'environ 1. Plus tard, cela a été prouvé analytiquement par Borgs, Chayes et Pittel .

Les vendeurs itinérants, Graph Colouring, Hamiltonian Cycle, entre autres, semblent également avoir des transitions de phase pour une paramétrisation appropriée de la création d'instances de problème. Je pense qu'il est prudent de dire qu'il est communément admis que tous les problèmes NP-Complete présentent une transition de phase pour un paramétrage approprié.

Associé à (certains) modèles de bruit pour le calcul quantique est une valeur seuil pour le niveau de bruit, au-dessus de laquelle les portes bruyantes peuvent être simulées par les portes Clifford, de sorte que les processus de calcul quantique deviennent efficacement simulables. Pour commencer, voir Plenio et Virmani, Limites supérieures sur les seuils de tolérance aux pannes des ordinateurs quantiques bruyants basés sur Cli ord (arXiv: 0810.4340v1).

Des modèles solubles comme celui-ci nous informent sur un problème pratique omniprésent: pour un système quantique physique spécifié en contact avec un réservoir thermique (éventuellement à température nulle), les niveaux de bruit associés à ce réservoir thermique sont-ils inférieurs ou supérieurs au seuil pour une simulation efficace avec un classique Ressources? Dans ce dernier cas, quels algorithmes de simulation sont optimaux?

$k$$k$$k$

$f(k)$$k$$f(k)$$2^k$$k$$1 \le f(k) < 2^k$

$k$$n$$k$$f(k)/2^k$

$f(k)$$f(k)+1$

• Jan Kratochvíl, Petr Savický et Zsolt Tuza, Une occurrence de plus de variables fait passer la satisfaction de Trivial à NP-Complete , SIAM J. Comput. 22 (1) 203–210, 1993. doi: 10.1137 / 0222015

$f(k)$$f(k) = \Theta(2^k/k)$

• Heidi Gebauer, Disproof of the Neighborhood conjecture with implications to SAT , Combinatorica 32 (5) 573–587, 2012. doi: 10.1007 / s00493-012-2679-y (préimpression)
• Heidi Gebauer, Tibor Szabó, Gábor Tardos, Le lemme local est serré pour SAT , SODA 2011.