¿Cuáles son las subfamilias # P-complete de # 2-SAT?

Version corta.

La prueba original de que # 2-SAT es # P- completo muestra, de hecho, que esas instancias de # 2-SAT son monótonas (no implican negaciones de ninguna variable) y bipartitas (el gráfico formado por las cláusulas sobre el variables es un gráfico bipartito) son #P -duro. Por lo tanto, los dos casos especiales # 2-MONOTONE-SAT y # 2-BIPARTITE-SAT son #P -hard. ¿Existen otros casos especiales que puedan caracterizarse en términos de propiedades 'naturales' de la fórmula, que también son #P -duro?

Versión larga.

El problema # 2-SAT es la tarea de computación: para una fórmula booleana $\phi$ consiste en la conjunción de varias cláusulas, donde cada cláusula es una disyunción de dos literales o , el número de cadenas booleanas tal que . Averiguar si existe o no tal es fácil; pero contar el número de soluciones en general es # P -completo, como lo muestra Valiant en The Complexity of Enumeration and Reliability Problems, SIAM J. Comput., 8 , pp. 410-421 .ˉ x j x ∈ { 0 , 1 } n ϕ ( x ) = $x_j$$\bar x_j$$x \in \{0,1\}^n$$\phi(x) = 1$$x$

Para el caso del # 2-SAT en particular, lo que Valiant realmente muestra es una reducción al # 2-SAT de contar coincidencias (incluidas las imperfectas) en gráficos bipartitos, lo que da lugar a instancias del # 2-SAT con una estructura muy particular , como sigue.

1. Primero, tenga en cuenta que el problema monótono es equivalente, por sustitución, al problema en el que para cada variable , aparece en la fórmula o pero no ambos. En particular, el problema de "disminución monótona" en el que solo ocurren las negaciones para cada variable es exactamente tan difícil como el caso monótono.x j ϕ ˉ x$x_j$$x_j$$\phi$$\bar x_j$$\bar x_j$

2. Para cualquier gráfico con aristas, podemos construir una fórmula monótona 2-SAT decreciente correspondiente a las coincidencias, colecciones de aristas que no comparten vértices, asignando una variable a cada arista, que representa si se incluye en un conjunto de bordes; la propiedad de un conjunto es una coincidencia es equivalente al vector de incidencia satisface la fórmula CNF cuyas cláusulas están dadas por para cada par de bordes que comparten un vértice. Por construcción, tiene tantas soluciones satisfactoriasm x e M ⊆ E x = χ M ϕ ( ˉ x e ∨ ˉ x f ) e , f ∈ E ϕ x ∈ { 0 , 1 } $G = (V,E)$$m$$x_e$$M \subseteq E$$\mathbf x = \chi_M$$\phi$$(\bar x_e \vee \bar x_f)$$e, f \in E$$\phi$$\mathbf x \in \{0,1\}^m$como hay (posiblemente imperfectos) matchings en el gráfico .$G$

3. Si el gráfico para el que queremos contar las coincidencias es bipartito, entonces no contiene ciclos impares, que podemos describir como una secuencia de bordes en el gráfico que comienza y termina con el mismo borde (sin contar ese borde final dos veces) . Entonces no hay secuencia de variables de longitud impar en , en las que las variables adyacentes están involucradas en una cláusula común. Entonces la fórmula sería bipartita de la manera descrita anteriormente.$G$ ϕ $x_e, x_f, x_g, \ldots, x_e$$\phi$$\phi$

4. Se puede contar el número de coincidencias en gráficos bipartitos arbitrarios, en particular, para contar el número de coincidencias perfectas en un gráfico bipartito: dado un gráfico de bitrarita de entrada con dos biparticiones de el mismo tamaño , uno puede crear gráficos mediante el aumento de con cualquier lugar vértices adicionales conectados a todos los vértices de . Debido a que todas las coincidencias en de un tamaño dado contribuyen de manera diferente a la cantidad de coincidencias en , al contarlas se puede determinar la cantidad de coincidencias en de tamañoA , B n G k A 0 ⩽ k ⩽ n B G G k G n { 0 , 1 $G = (A \cup B, E)$$A, B$$n$$G_k$$A$$0 \leqslant k \leqslant n$$B$$G$$G_k$$G$$n$(es decir, que son combinaciones perfectas); y tenga en cuenta que contar el número de coincidencias perfectas en gráficos bipartitos es equivalente a calcular los permanentes de -matrices por una simple correspondencia.$\{0,1\}$

La clase de instancias de # 2-SAT que se muestran como #P -hard son las instancias bipartitas monótonas.

Pregunta: ¿Cuáles son los otros casos especiales de # 2-SAT que son # P- completos, como resultado de esta o alguna otra reducción?

Sería interesante si, además de mostrar / citar una reducción, las personas también pudieran describir una razón intuitiva de cómo el caso especial podría proporcionar obstáculos a los enfoques naturales para contar las tareas satificantes. Por ejemplo, aunque MONOTONE-2-SAT es trivialmente solucionable ( es siempre una solución), las instancias monótonas son aquellas en las que la asignación de alguna variable a un valor fijo fallará rutinariamente al imponer muchas restricciones al resto variables La fijación de cualquier variable solo restringe los valores de las variables inmediatamente relacionadas con ella mediante alguna cláusula; y configurandox j = 0 x j = $\mathbf x = 1^n$$x_j = 0$$x_j = 1$no restringe los posibles valores de ninguna otra variable. (Sin embargo, no está claro que la restricción comparable a los gráficos bipartitos sea significativa de la misma manera; la restricción bipartita parece agregar estructura en lugar de eliminarla, pero no agrega la estructura suficiente para contar de manera eficiente).

Editado para agregar. Los puntos de bonificación se otorgarán por tal clase que no lo hace en última instancia depende de la existencia de casos monótonas (como # 2-Bipartita-SAT hace más arriba, cuya dureza es al parecer debido a la inclusión de la #P -Hard caso especial # 2 -MONOTONE-BIPARTITE-SAT). Por ejemplo, sería interesante un argumento sobre la dureza del # 2-BIPARTITE-SAT que no se basa en instancias monótonas (pero podría depender de alguna otra subfamilia).

# 3-La cubierta de vértice plana bipartita regular es # P-completa

Como contar las cubiertas de vértices es exactamente lo mismo que contar las tareas satisfactorias de una instancia monótona # 2-SAT, el resultado anterior implica que es # P-completo contar las tareas satisfactorias de una instancia # 2-SAT que es monótona y 3-regular y bipartito y plano .

Esto a su vez significa que, además de los dos casos especiales # 2-MONOTONE-SAT y # 2-BIPARTITE-SAT ya citados en la pregunta, los dos casos especiales # 2-CUBIC-SAT y # 2-PLANAR-SAT son # P-completo también.