Soluciones de conteo de fórmulas Monotone-2CNF

Una fórmula Monotone-2CNF es una fórmula CNF donde cada cláusula está compuesta por exactamente 2 literales positivos.

Ahora, tengo una fórmula Monótono-2CNF . Sea S el conjunto de las tareas satisfactorias de F. También tengo un oráculo O que puede dar la siguiente información:$F$$S$$F$$O$

1. La cardinalidad del conjunto (es decir, el número de soluciones de F ).$S$$F$
2. Dada una variable : $x$
   • El número de soluciones en contienen el literal positivo x .$S$$x$
   • El número de soluciones en contienen el literal negativo ¬ x .$S$$\lnot x$
3. Dadas 2 variables y x 2 : $x_1$$x_2$
   • El número de soluciones en contienen x 1 ∧ x 2 .$S$$x_1 \land x_2$
   • El número de soluciones en contienen x 1 ∧ ¬ x 2 .$S$$x_1 \land \lnot x_2$
   • El número de soluciones en contienen ¬ x 1 ∧ x 2 .$S$$\lnot x_1 \land x_2$
   • El número de soluciones en contienen ¬ x 1 ∧ ¬ $S$ .$\lnot x_1 \land \lnot x_2$

Tenga en cuenta que el oráculo es "limitado": funciona solo en F , no se puede usar en una fórmula F ′$O$$F$ .$F' \neq F$

Pregunta:

Dadas 3 variables , x 2 , x 3 es posible determinar el número de soluciones en S que contienen ¬ x 1 ∧ ¬ x 2 ∧ ¬ x 3 en tiempo polinómico, usando $x_1$$x_2$$x_3$$S$$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$F$ y la información proporcionada por ?$O$

Nota:

Puede reemplazar en la pregunta con cualquier otra de las 8 combinaciones posibles de x 1 , x 2 , x 3 . El problema seguiría siendo el mismo.$\lnot x_1 \land \lnot x_2 \land \lnot x_3$$x_1$$x_2$$x_3$

Hecho empírico:

Me encontré con el siguiente hecho empírico hace una semana. Sea el conjunto de las soluciones que contienen ¬ x 1 ∧ ¬ x 2 , y sea S ¬ x 1 ∧ ¬ x 2 ∧ x 3 ⊂ S el conjunto de las soluciones que contienen ¬ x 1 ∧ ¬ x 2 ∧ x 3 . Ahora, parece ser el caso que, si la condición $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$ cumple, esta relación también se cumple:

dondeϕ=1.618033 ...es la proporción áurea. La condiciónCparece ser la siguiente:"x1,x2,x3se mencionan enFcasi el mismo número de veces".$\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$

Para usar ese hecho empírico, realmente desea saber si los números aproximados pueden dar a otros números aproximados. Pero para el caso exacto, creo que puede haber una manera directa de mostrar que esto es difícil. Aquí hay un boceto.

Primero tenga en cuenta que las asignaciones satisfactorias corresponden a conjuntos independientes en un gráfico. Voy a utilizar la frase "S-proyecciones de I (G)" para describir la correlación de funciones al número de conjuntos independientes de I con I ∩ S = T . Las "proyecciones k" son las proyecciones S para todos los subconjuntos S de V con | S | = k .$T \subset S$$I \cap S = T$$|S|=k$

Esquema de prueba:

1. Si las 2 proyecciones dan 3 proyecciones, también dan k proyecciones en polytime para cada k.
2. Si las 2 proyecciones dan 4 proyecciones, entonces el número de conjuntos independientes de un gráfico está en FP, entonces 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}$.

$G'$$G'$$G'$${x_1,...,x_k,v}$

${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|$?