A Monotone-2CNF formula is a CNF formula where each clause is composed by exactly 2 positive literals.
Now, I have a Monotone-2CNF formula $F$. Let $S$ be the set of $F$'s satisfying assignments. I also have an oracle $O$ which is able to give the following information:
- The cardinality of the set $S$ (i.e. the number of solutions of $F$).
-
Given a variable $x$:
- The number of solutions in $S$ containing the positive literal $x$.
- The number of solutions in $S$ containing the negative literal $\lnot x$.
-
Given 2 variables $x_1$ and $x_2$:
- The number of solutions in $S$ containing $x_1 \land x_2$.
- The number of solutions in $S$ containing $x_1 \land \lnot x_2$.
- The number of solutions in $S$ containing $\lnot x_1 \land x_2$.
- The number of solutions in $S$ containing $\lnot x_1 \land \lnot x_2$.
Note that the oracle $O$ is "limited": it works only on $F$, it can't be used on a formula $F' \neq F$.
Question:
Given 3 variables $x_1$, $x_2$, $x_3$ is it possible to determine the number of solutions in $S$ containing $\lnot x_1 \land \lnot x_2 \land \lnot x_3$ in polynomial time, using $F$ and the information provided by $O$?
Note:
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$ holds, this relationship also holds:
$\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".