Solutions de comptage des formules Monotone-2CNF

Une formule Monotone-2CNF est une formule CNF où chaque clause est composée d'exactement 2 littéraux positifs.

Maintenant, j'ai une formule Monotone-2CNF $F$. Soit $S$ l'ensemble des affectations satisfaisantes de $F$J'ai également un oracle qui est capable de donner les informations suivantes:$O$

1. La cardinalité de l'ensemble (ie le nombre de solutions de ).$S$$F$
2. Étant donné une variable : $x$
   • Le nombre de solutions dans contenant le littéral positif .$S$$x$
   • Le nombre de solutions dans contenant le littéral négatif .$S$$\lnot x$
3. Étant donné 2 variables et : $x_1$$x_2$
   • Le nombre de solutions dans contenant .$S$$x_1 \land x_2$
   • Le nombre de solutions dans contenant .$S$$x_1 \land \lnot x_2$
   • Le nombre de solutions dans contenant .$S$$\lnot x_1 \land x_2$
   • Le nombre de solutions dans contenant .$S$$\lnot x_1 \land \lnot x_2$

A noter que l'oracle est "limité": il ne fonctionne que sur$O$$F$ , il ne peut pas être utilisé sur une formule .$F' \neq F$

Question:

Étant donné 3 variables , , , il est possible de déterminer le nombre de solutions dans contenant en temps polynomial, en utilisant$x_1$$x_2$$x_3$$S$$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$F$ et les informations fournies par ?$O$

Remarque:

Vous pouvez remplacer dans la question par n'importe quelle autre des 8 combinaisons possibles de x 1 , x 2 , x 3 . Le problème resterait le même.$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$x_1$$x_2$$x_3$

Fait empirique:

Je suis tombé sur le fait empirique suivant il y a une semaine. Soit l'ensemble des solutions contenant ¬ x 1 ∧ ¬ x 2 , et soit S ¬ x 1 ∧ ¬ x 2 ∧ x 3 ⊂ S l'ensemble des solutions contenant ¬ x 1 ∧ ¬ x 2 ∧ x 3 . Maintenant, il semble que si la condition $S_{\lnot x_1 \land \lnot x_2} \subset S$$\lnot x_1 \land \lnot x_2$$S_{\lnot x_1 \land \lnot x_2 \land x_3} \subset S$$\lnot x_1 \land \lnot x_2 \land x_3$$C$détient, cette relation est également valable:

oùϕ=1,618033 ...est le nombre d'or. La conditionCsemble être la suivante:"x1,x2,x3sont mentionnés enFpresqueautantde fois".$\frac{|S_{\lnot x_1 \land \lnot x_2}|}{|S_{\lnot x_1 \land \lnot x_2 \land x_3}|} \simeq \phi$

$\phi = 1.618033...$$C$$x_1$$x_2$$x_3$$F$

Pour utiliser ce fait empirique, vous voulez vraiment savoir si des nombres approximatifs peuvent donner à d'autres des nombres approximatifs. Mais pour le cas exact, je pense qu'il peut y avoir un moyen simple de montrer que c'est difficile. Voici un croquis.

Notez d'abord que les affectations satisfaisantes correspondent à des ensembles indépendants dans un graphique. Je vais utiliser l'expression "S-I de projections (G)" pour décrire le mappage de fonction au nombre d'ensembles indépendants I avec I ∩ S = T . Les "k-projections" sont les projections S pour tous les sous-ensembles S de V avec | S | = k .$T \subset S$$I \cap S = T$$|S|=k$

Aperçu de la preuve:

1. Si 2 projections donnent 3 projections, elles donnent également k projections en polytemps pour chaque k.
2. Si 2 projections donnent 4 projections, alors le nombre d'ensembles indépendants d'un graphe est en FP, donc FP = # P.

(1) Soit tel que les projections (k-1) donnent k-projections. Étant donné un graphe, les k-projections, et x 1 , . . . , X k , v ∈ G , on calcule les projections sur x 1 , . . . , x k , v .$k\geq 3$$x_1,...,x_k,v \in G$${x_1,...,x_k,v}$

Définissez le graphique en attachant un nouveau sommet à v. Cela peut être considéré comme une pondération v. Les projections (k-1) de G ′ peuvent être calculées parce que nous connaissons les k-projections de G. k-projections de G ′ . Et cela donne x 1 , . . . , x k , v- projections de G.$G'$$G'$$G'$${x_1,...,x_k,v}$

(2) Etant donné un graphe, l' ordre des bords l' et définir G k pour avoir des bords e 1 , . . . , e k . Les 2 projections de G k + 1 peuvent être calculées à partir des 4 projections de G k . Le nombre d'ensembles indépendants dans G 0 est 2 | G | . Itérativement, les 4 projections de G peuvent être calculées en temps polynomial.${e_1,...,e_m}$$G_k$${e_1,...,e_k}$$G_{k+1}$$G_k$$G_0$$2^{|G|}$

Quelques observations, pas une réponse.

Suite à la note à la question, toute combinaison de 3 littéraux peut être exprimée en termes de toute autre combinaison de littéraux sur les mêmes variables, ainsi qu'un petit nombre de termes que l'oracle peut fournir. Cela découle de l'examen du diagramme de Venn de 3 ensembles qui se croisent et de l'expression de chacune des 8 régions en fonction des autres régions. Notez que cela ne nécessite pas que la formule soit monotone ou 2CNF.

Il est également clair que le nombre de solutions satisfaisant tout conjoncture à 3 littéraux peut être exprimé comme la somme de termes, chacun étant soit 0 soit 1, exprimant une affectation particulière à toutes les variables. Chacun de ceux-ci peut être évalué en temps linéaire, mais il y a de manière exponentielle de nombreux termes à évaluer, donc cela ne satisfait pas aux exigences.$2^{n-3}$

Par conséquent, la question est vraiment de savoir s'il est possible d'exploiter la propriété d'être 2CNF monotone pour compresser cette expression de taille exponentielle en taille polynomiale.

J'ai essayé de regarder une question plus simple, en limitant l'oracle à une chaîne de conseils avec le nombre de solutions, lorsque le nombre de combinaisons littérales simples ou par paires n'est pas disponible. Je ne vois aucun moyen d'exploiter la connaissance du nombre de solutions pour obtenir un calcul rapide du nombre de solutions par rapport à n'importe quel littéral.

Y a-t-il quelque chose au sujet du 2CNF monotone qui permettrait d' obtenir rapidement le nombre de solutions dans contenant x 1 , si l'on savait | S | ?$S$$x_1$$|S|$