Que savons-nous de la transition de phase des problèmes # P-Complete?

11

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 à difficile et de nouveau à facile. Je voudrais savoir s'il existe également un tel phénomène pour les problèmes # P-Complete. Plus important encore, s'il existe une transition de phase, est-ce la même chose pour # CNF-k-SAT et # DNF-k-SAT?

Je pense qu'il existe un certain type de transition de phase pour # CNF-k-SAT. D'un autre côté, je ne pense pas qu'il y ait de transition de phase pour # DNF-k-SAT et le problème devient plus difficile à mesure que nous ajoutons plus de clauses ....

cc.complexity-theory counting-complexity phase-transition Tayfun Pay
la source
1
Pourriez-vous clarifier un peu ce que vous entendez par "la" transition de phase #P? La transition de phase pour les problèmes NP-Complete est généralement considérée comme la probabilité qu'une instance aléatoire tirée d'une distribution paramétrée soit satisfaisable (pour 3-SAT, par exemple). Quelle est la transition pour #P? Quand un certain pourcentage est-il satisfaisable?
user834
Veuillez également spécifier si vous essayez de calculer la valeur exacte ou si vous autorisez des valeurs approximatives.
Tyson Williams
1
"le problème passe de facile à difficile et de nouveau à difficile" Vous voulez dire "facile à difficile et à nouveau facile"?
Tyson Williams
1
Je ne sais toujours pas quelle quantité vous mesurez. La transition de phase 3-SAT (par exemple pour le concret) est considérée comme la probabilité qu'une solution existe. ie d'au moins une solution existante. Donc, si "la" transition #P est supposée signifier la probabilité d'un nombre de solutions non nul, alors ces deux sont équivalentes. En outre, il existe une différence entre «facile» et «une solution existante», car le premier implique un algorithme polynomial, contrairement au second. La centrale nucléaire est connue pour être difficile presque partout, même loin du point de transition.
user834

Réponses:

7

Pour compter les ensembles indépendants, il y a une preuve récente pour une transition de phase de calcul, par Allan Sly: http://arxiv.org/abs/1005.5584 (l'algorithme est de Dror Weitz de 2006; Allan a prouvé la dureté correspondante et a gagné le meilleur article de FOCS'10 pour cela)

Notez que pour 3SAT aléatoires et des problèmes similaires, il n'y a aucune preuve que ces problèmes sont effectivement difficiles dans l'intervalle approprié. Lorsque vous passez aux problèmes de comptage les plus difficiles, il devient plus facile de prouver la dureté.

Dana Moshkovitz
la source