Quelles sont les sous-familles # P-complètes de # 2-SAT?

Version courte.

La preuve originale que # 2-SAT est #P -complete montre, en fait, que les instances de # 2-SAT qui sont à la fois monotones (n'impliquant la négation d'aucune variable) et bipartites (le graphique formé par les clauses sur le est un graphe bipartite) sont #P -hard. Ainsi, les deux cas particuliers # 2-MONOTONE-SAT et # 2-BIPARTITE-SAT sont #P -hard. Y at - il d' autres cas particuliers qui peuvent être caractérisés en termes de propriétés « naturelles » de la formule, qui sont également #P -hard?

Version longue.

Le problème # 2-SAT est la tâche de calculer - pour une formule booléenne $\phi$ consistant en la conjonction de plusieurs clauses, où chaque clause est une disjonction de deux littéraux $x_j$ ou $\bar x_j$ - le nombre de chaînes booléennes $x \in \{0,1\}^n$ tel que $\phi(x) = 1$ . Il est facile de savoir s'il existe ou non un tel $x$ ; mais compter le nombre de solutions en général est # P-complet, comme le montre Valiant dansLa complexité des problèmes d'énumération et de fiabilité, SIAM J. Comput., 8 , pp. 410–421 .

Pour le cas de # 2-SAT en particulier, ce que Valiant montre en réalité est une réduction à # 2-SAT du comptage des correspondances (y compris celles imparfaites) dans les graphiques bipartites, ce qui donne lieu à des instances de # 2-SAT avec une structure très particulière , comme suit.

1. Notons tout d'abord que le problème monotone est équivalent, par substitution, au problème dans lequel pour chaque variable , soit x j apparaît dans la formule ϕ soit ˉ x j mais pas les deux. En particulier, le problème "monotone décroissant" dans lequel seules les négations ˉ x j se produisent pour chaque variable est exactement aussi difficile que le cas monotone.$x_j$$x_j$$\phi$$\bar x_j$$\bar x_j$

2. Pour tout graphique avec m arêtes, nous pouvons construire une formule 2-SAT monotone décroissante correspondant à des correspondances - collections d'arêtes qui ne partagent aucun sommet - en affectant une variable x e à chaque arête, représentant s'il est inclus dans un jeu de bords; la propriété d'un ensemble M ⊆ E étant une correspondance est équivalente au vecteur d'incidence x = χ M satisfaisant la formule CNF ϕ dont les clauses sont données par ( ˉ x e ∨ ˉ x f$G = (V,E)$$m$$x_e$$M \subseteq E$$\mathbf x = \chi_M$$\phi$$(\bar x_e \vee \bar x_f)$pour chaque paire d'arêtes qui partagent un sommet. Par construction, φ a autant de solutions satisfaisant x ∈ { 0 , 1 } m comme il y a (peut - être imparfaite) appariements dans le graphe G .$e, f \in E$$\phi$$\mathbf x \in \{0,1\}^m$$G$

3. Si le graphique pour lequel nous voulons compter les correspondances est bipartite, il ne contient aucun cycle impair - que nous pouvons décrire comme une séquence d' arêtes dans le graphique qui commence et se termine par le même bord (sans compter deux fois ce dernier bord) . Il n'y a alors pas de séquence de variables x e , x f , x g , … , x e de longueur impaire dans ϕ , dans lesquelles des variables adjacentes sont impliquées dans une clause commune. La formule ϕ serait alors bipartite de la manière décrite précédemment.$G$$x_e, x_f, x_g, \ldots, x_e$$\phi$$\phi$

4. Le comptage du nombre de correspondances dans des graphes bipartites arbitraires, en particulier, peut être utilisé pour compter le nombre de correspondances parfaites dans un graphe bipartite: étant donné un graphe bitrarite d'entrée avec deux bipartitions A , B de la même taille n , on peut créer des graphiques G k en augmentant A avec partout 0 ⩽ k ⩽ n sommets supplémentaires reliés à tous les sommets de B . Parce que toutes les correspondances en $G = (A \cup B, E)$$A, B$$n$$G_k$$A$$0 \leqslant k \leqslant n$$B$$G$d'une taille donnée contribuent différemment au nombre d'appariements dans , en les comptant, on peut déterminer le nombre d'appariements dans G de taille n (c'est-à-dire qui sont des appariements parfaits); et notons que compter le nombre de correspondances parfaites dans les graphes bipartis équivaut à calculer des permanents de matrices { 0 , 1 } par une simple correspondance.$G_k$$G$$n$$\{0,1\}$

La classe d'instances de # 2-SAT qui se révèlent être #P -hard sont alors les instances bipartites monotones.

Question: Quels sont les autres cas particuliers de # 2-SAT qui sont # P- complets, à la suite de cette réduction ou d'une autre réduction?

Il serait intéressant que, en plus de montrer / citer une réduction, les gens puissent également décrire une raison intuitive pour expliquer comment le cas spécial pourrait constituer des obstacles aux approches naturelles pour compter les affectations de saturation. Par exemple, bien que MONOTONE-2-SAT soit trivialement résoluble ( est toujours une solution), les instances monotones sont celles dans lesquelles l'attribution d'une variable à une valeur fixe échouera régulièrement à imposer de nombreuses contraintes aux variables restantes. Fixer n'importe quelle variable x j = 0 ne restreint que les valeurs des variables qui lui sont immédiatement liées par une clause; et fixant x j = $\mathbf x = 1^n$$x_j = 0$$x_j = 1$ne restreint pas du tout les valeurs possibles des autres variables. (Il n'est pas clair cependant que la restriction comparable aux graphiques bipartites soit significative de la même manière; la restriction bipartite semble ajouter de la structure plutôt que la supprimer, mais elle ne permet pas d'ajouter suffisamment de structure pour compter efficacement.)

Modifié pour ajouter. Des points bonus seront attribués pour toute classe de ce type qui ne dépend pas en fin de compte de l'existence d'instances monotones (comme le fait # 2-BIPARTITE-SAT ci-dessus, dont la dureté est apparemment due à l'inclusion du cas spécial #P -hard # 2 -MONOTONE-BIPARTITE-SAT). Par exemple, un argument pour la dureté de # 2-BIPARTITE-SAT qui ne repose pas sur des instances monotones (mais pourrait s'appuyer sur une autre sous-famille) serait intéressant.

# 3-Le couvercle bipartite régulier en sommet planaire est # P-complet

Comme le comptage des couvertures de sommets est exactement le même que le comptage des affectations satisfaisantes d'une instance monotone # 2-SAT, le résultat ci-dessus implique qu'il est # P-complet de compter les affectations satisfaisantes d'une instance # 2-SAT qui est monotone et 3-régulière. et bipartite et planaire .

Cela signifie que, outre les deux cas spéciaux # 2-MONOTONE-SAT et # 2-BIPARTITE-SAT déjà cités dans la question, les deux cas spéciaux # 2-CUBIC-SAT et # 2-PLANAR-SAT sont # P-complet aussi.