Une question à la preuve # P-complète du permanent de Ben-Dor / Halevi

14

Dans l'article de Ben-Dor / Halevi [1], il est donné une autre preuve que le permanent est #P complet. Dans la dernière partie de l'article, ils montrent la chaîne de réduction

IntPermNoNegPerm2PowersPerm0/1-Perm
tandis que la valeur permanente est préservée le long de la chaîne. Étant donné que le nombre d'affectations satisfaisantes d'une formule 3SAT peut être obtenu à partir de la valeur permanente, il suffit de calculer le permanent de la matrice finale . Jusqu'ici tout va bien.Φ0/1

Cependant, il est bien connu que le permanent d'une matrice est égal au nombre de correspondances parfaites dans la double couverture bipartite0/1AG , c'est-à-dire le graphique de la matrice . Et ce nombre peut être calculé efficacement si G s'avère être planaire (en utilisant l'algorithme de Kastelyens).(0AAt0)G

Donc, au total, cela signifie que quelqu'un pourrait calculer le nombre d'affectations satisfaisantes d'une formule booléenne si le graphe final est plan.ΦG

Étant donné que l'incorporation de dépend fortement de la formule , l'espoir est qu'il existe certaines formules qui mènent plus souvent dans des couvertures bipartites planes. Est-ce que quelqu'un sait s'il a déjà été étudié quelle est la probabilité que soit planaire?GΦG

Étant donné que le comptage des solutions de satiesfying est -complet, les graphiques seront à coup sûr presque toujours non plans, mais je ne trouve aucun indice concernant ce sujet.#P

[1] Amir Ben-Dor et Shai Halevi. Zero-one permanent est # p-complete, une preuve plus simple. In 2nd Israel Symposium on Theory of Computing Systems, pages 108-117, 1993. Natanya, Israël.

Etsch
la source

Réponses:

11

Ce sujet a été largement étudié ces dernières années sous le nom d' algorithmes holographiques par des chercheurs tels que Valiant, Cai, Lu, Xia, Lipton et autres. Essentiellement, tous les cas traitables de #CSP (problèmes de satisfaction des contraintes de comptage) ont été identifiés en termes de théorèmes de dichotomie (FP vs # P-complete). En particulier, les calculs Matchgate ont été identifiés comme la classe spécifique de problèmes de comptage qui deviennent traitables sur les graphiques planaires . Voir par exemple ce lien pour d'autres références.

Martin Schwarz
la source
1
Merci Martin pour la réponse. Le document que vous avez lié vaut quand même la peine d'être lu. Cependant, il ne mentionne pas une relation de la forme . La matrice A ni son graphe biparti à double couverture G sont aléatoires, mais dépendent entièrement de la structure de Φ et des gadgets graphiques utilisés. La question est donc plutôt sur la classification des formules Φ qui conduisent à des graphes planaires G et qui ne le sont pas. (Il existe en effet des formules qui seront planes, puisque nous avons implémenté tout l'algorithme)ΦUNEgUNEgΦΦg
Etsch
2

Normalement, un problème #CSP non pondéré est défini par un ensemble de relations et l'entrée du problème #CSP ( Γ ) est une formule Φ .ΓΓΦ

Si ne contient que des relations d'arité au plus 1, alors chaque entrée possible Φ correspond à un graphe avec des graphes en étoile disjoints, qui est plan. De plus, si Γ contient une relation d'arité 2 ou plus, alors il est facile de construire des instances qui ne sont pas planes. (Considérez les variables comme les sommets d'un graphique et les contraintes binaires comme des arêtes entre ces sommets de variables. Une plus grande arité contient également du travail. De cette façon, n'importe quel graphique peut être construit, au moins comme un sous-graphique d'un autre graphique.)ΓΦΓ

En contraste, vous ignorez et demandez directement sur quels Φ conduisent à des graphiques planaires. Cependant, chaque Φ définit un graphique (unique). Il n'y a pas d'incertitude comme vous le suggérez dans ce paragraphe:ΓΦΦ

Étant donné que l'incorporation de dépend fortement de la formule Φ , l'espoir est qu'il existe certaines formules qui mènent plus souvent dans des couvertures bipartites planes. Est-ce que quelqu'un sait s'il a déjà été étudié quelle est la probabilité que G soit planaire?gΦg

Tyson Williams
la source