Je cherche des exemples de problèmes paramétrés par un nombre , où la dureté du problème est non monotone en . La plupart des problèmes (selon mon expérience) ont une transition de phase unique, par exemple -SAT a une transition de phase unique de (où le problème est en P) à (où le le problème est...
Une caractéristique bien connue des instances -SAT est le rapport du nombre de clauses sur le nombre de variables n , c'est-à-dire le quotient \ rho = m / n . Pour chaque k , il existe une valeur seuil \ alpha st \ pour \ rho \ ll \ alpha , la plupart des instances sont satisfaisables et pour \ rho...
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 = p0p=p0p=p_0p = p1p=p1p=p_1p0p0p_0p1p1p_1 Un exemple est le comptage des configurations de spin sur les...
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...
Le rapport critique des clauses aux variables pour le 3-SAT aléatoire est supérieur à 3 et inférieur à 6, et semble être communément décrit comme «autour de 4,2» ou «autour de 4,25». Mezard, Parisi et Zecchina prouvent (au sens physique) que le rapport critique est 4.256, tandis que les premier et...
Il existe 4 contraintes différentes que nous pouvons avoir lors de la définition de K-SAT aléatoire. 1) Le nombre total de littéraux dans une clause donnée est exactement K ou AT la plupart des K 2) Un littéral donné peut être utilisé avec ou sans remplacement dans la même clause (A ou A ou A) 3)...
Que sait-on de la transition de phase dans les problèmes # P-Complete? Spécifiquement, existe-t-il une transition de phase différente pour # DNF-k-SAT et # CNF-k-SAT? Mise à jour: Comme nous le savons, il y a une transition de phase dans Random k-SAT où la résolution du problème passe de facile à...
Je voudrais connaître l'état actuel de la transition de phase pour les k-sat aléatoires, étant donné n variables et m clauses, quel est le c = m / n le mieux connu pour les bornes supérieures et