Solusi penghitungan formula Monotone-2CNF

Rumus Monotone-2CNF adalah formula CNF di mana setiap klausa tersusun oleh tepat 2 literal positif.

Sekarang, saya memiliki Monoton-2CNF rumus . Misalkan S adalah himpunan tugas F yang memuaskan. Saya juga memiliki oracle O yang dapat memberikan informasi berikut:$F$$S$$F$$O$

1. Kardinalitas himpunan (yaitu jumlah solusi F ).$S$$F$
2. Diberikan variabel : $x$
   • Jumlah solusi dalam mengandung literal positif x .$S$$x$
   • Jumlah solusi dalam mengandung literal negatif ¬ x .$S$$\lnot x$
3. Diberikan 2 variabel dan x 2 : $x_1$$x_2$
   • Jumlah solusi dalam mengandung x 1 ∧ x 2 .$S$$x_1 \land x_2$
   • Jumlah solusi dalam mengandung x 1 ∧ ¬ x 2 .$S$$x_1 \land \lnot x_2$
   • Jumlah solusi dalam mengandung ¬ x 1 ∧ x 2 .$S$$\lnot x_1 \land x_2$
   • Jumlah solusi dalam mengandung ¬ x 1 ∧ ¬ x 2 .$S$$\lnot x_1 \land \lnot x_2$

Perhatikan bahwa oracle adalah "terbatas": ia bekerja hanya pada F , tidak dapat digunakan pada formula F ' ≠ F .$O$$F$$F' \neq F$

Pertanyaan:

Diberikan 3 variabel , x 2 , x 3 apakah mungkin untuk menentukan jumlah solusi dalam S yang mengandung ¬ x 1 ∧ ¬ x 2 ∧ ¬ x 3 dalam waktu polinomial, menggunakan F dan informasi yang diberikan oleh $x_1$$x_2$$x_3$$S$$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$F$$O$ ?

catatan:

You can replace $\lnot x_1 \land \lnot x_2 \land \lnot x_3$ in the question with whatever else of the 8 possible combinations of $x_1$, $x_2$, $x_3$. The problem would remain the same.

Empirical fact:

I came across the following empirical fact one week ago. Let $S_{\lnot x_1 \land \lnot x_2} \subset S$ be the set of those solutions containing $\lnot x_1 \land \lnot x_2$, and let $S_{\lnot x_1 \land \lnot x_2 \land x_3} \subset S$ be the set of those solutions containing $\lnot x_1 \land \lnot x_2 \land x_3$. Now, it seems to be the case that, if condition $C$

$\frac{|S_{\lnot x_1 \land \lnot x_2}|}{|S_{\lnot x_1 \land \lnot x_2 \land x_3}|} \simeq \phi$

where $\phi = 1.618033...$ is the golden ratio. Condition $C$ seems to be the following: "$x_1$, $x_2$, $x_3$ are mentioned in $F$ almost the same number of times".

To use that empirical fact you really want to know whether approximate numbers can give others approximate numbers. But for the exact case, I think there may be a straightforward way to show this is hard. Here's a sketch.

First note that satisfying assignments correspond to independent sets in a graph. I'll use the phrase "S-projections of I(G)" to describe the function mapping $T \subset S$ to the number of independent sets I with $I \cap S = T$. The "k-projections" are the S-projections for all subsets S of V with $|S|=k$.

Proof outline:

1. If 2-projections give 3-projections, they also give k-projections in polytime for each k.
2. If 2-projections give 4-projections, then the number of independent sets of a graph is in FP, so FP=#P.

(1) Let $k\geq 3$ such that (k-1)-projections give k-projections. Given a graph, its k-projections, and $x_1,...,x_k,v \in G$, we will compute the projections onto ${x_1,...,x_k,v}$.

Define the graph $G'$ by attaching a fresh vertex to v. This can be seen as weighting v. The (k-1)-projections of $G'$ can be computed because we know the k-projections of G. So then we have the k-projections of $G'$. And this gives ${x_1,...,x_k,v}$-projections of G.

(2) Given a graph, order the edges ${e_1,...,e_m}$ and define $G_k$ to have edges ${e_1,...,e_k}$. The 2-projections of $G_{k+1}$ can be computed from the 4-projections of $G_k$. The number of independent sets in $G_0$ is $2^{|G|}$. Iteratively the 4-projections of G can be computed in polynomial time.

Some observations, not an answer.

Further to the note to the question, any combination of 3 literals can be expressed in terms of any other combination of literals on the same variables, together with a small number of terms that the oracle can provide. This follows from looking at the Venn diagram of 3 intersecting sets, and expressing each of the 8 regions in terms of the other regions. Note that this does not require the formula to be either monotone or 2CNF.

It is also clear that the number of solutions satisfying any 3-literal conjunct can be expressed as the sum of $2^{n-3}$ terms, each of which is either 0 or 1, expressing a particular assignment to all variables. Each of these can be evaluated in linear time, but there are exponentially many terms to evaluate, so this doesn't satisfy the requirements.

Hence the question is really about whether it is possible to exploit the property of being monotone 2CNF to compress this exponential-size expression to polynomial size.

I tried to look at a simpler question, restricting the oracle to just an advice string with the number of solutions, when the counts for single or pairwise literal combinations are not available. I cannot see any way to exploit knowledge of the number of solutions to obtain a quick calculation of the number of solutions with respect to any single literal.

Is there something about monotone 2CNF that would allow the number of solutions in $S$ containing $x_1$ to be obtained quickly, if one knew $|S|$?