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

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

Cependant, il est bien connu que le permanent d'une matrice est égal au nombre de correspondances parfaites dans la double couverture bipartite$0/1$$\text{A}$$G$ , 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).$\begin{pmatrix} 0 & \text{A} \\ \text{A}^t & 0 \end{pmatrix}$$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.$\Phi$$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$$\Phi$$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.

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.

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 Φ .$\Gamma$$\Gamma$$\Phi$

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.)$\Gamma$$\Phi$$\Gamma$

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:$\Gamma$$\Phi$$\Phi$

É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$$\Phi$$G$