Satisfacción de fórmulas booleanas generales con un máximo de dos ocurrencias por variable

Question

(Si tiene conocimientos básicos de informática teórica, puede pasar inmediatamente al recuadro oscuro de más abajo. He pensado intentar explicar mi pregunta con mucho cuidado, para maximizar el número de personas que la entiendan).

Decimos que a Fórmula booleana es una fórmula proposicional sobre algunas variables 0-1 $x_1,\ldots,x_n$ que implican las conectivas AND y OR, donde los átomos son literales que son instancias de $x_i$ o $\neg x_i$ para algunos $i$ . Es decir, una fórmula booleana es una fórmula "monótona" sobre las $2n$ átomos $x_1,\ldots, x_n, \neg x_1,\ldots, \neg x_n$ . Por ejemplo, $$((\neg x_1 ~OR~ x_2) ~AND~ (\neg x_2 ~OR~ x_1)) ~OR~ x_3$$ es una fórmula booleana que expresa que o bien $x_1$ y $x_2$ toman el mismo valor, o $x_3$ debe ser $1$ . Decimos que una asignación 0-1 a las variables de una fórmula es satisfaciendo si la fórmula se evalúa como $1$ en la tarea.

El teorema de Cook-Levin dice que el general Satisfacción de fórmulas booleanas problema es $NP$ -completa: dada una fórmula arbitraria, es $NP$ -difícil encontrar una tarea satisfactoria para él. De hecho, incluso las fórmulas booleanas satisfactorias en las que cada variable $x_i$ aparece como máximo tres veces en la fórmula es $NP$ -completa. (He aquí una reducción del caso general a este caso: Supongamos una variable $x$ aparece $k > 3$ veces. Sustituye cada una de sus apariciones por nuevas variables $x^1, x^2, \ldots, x^k$ y limitarlas $k$ para que todas las variables tengan el mismo valor, juntando la fórmula con $$(\neg x^1 ~OR~ x^2) ~AND~ (\neg x^2 ~OR~ x^3) ~AND~ \cdots ~AND~ (\neg x^{k-1} ~OR~ x^k) ~AND~ (\neg x^k ~OR~ x^1).$$ Número total de apariciones de cada variable $x^j$ es ahora de tres). Por otra parte, si cada variable aparece una sola vez en la fórmula, entonces el algoritmo de la satisfabilidad es muy fácil: como tenemos una fórmula monótona en $x_1,\ldots, x_n, \neg x_1,\ldots, \neg x_n$ fijamos $x_i$ a $0$ si $\neg x_i$ de lo contrario, fijamos $x_i$ a $1$ . Si esta asignación no consigue que la fórmula salga $1$ entonces ninguna asignación lo hará.

Mi pregunta es, supongamos que cada variable aparece como máximo dos veces en una fórmula booleana general. ¿Es el problema de satisfacción para esta clase de fórmulas $NP$ -¿completa o resoluble en tiempo polinómico?

EDIT: Para mayor claridad, he aquí un ejemplo del problema: $$((x_1 ~AND~ x_3) ~OR~ (x_2 ~AND~ x_4 ~AND~ x_5)) ~AND~ (\neg x_1 ~OR~ \neg x_4) ~AND~ (\neg x_2 ~OR~ (\neg x_3 ~AND~ \neg x_5))$$

Obsérvese que si restringimos la clase de fórmulas a la forma normal conjuntiva (es decir, un circuito de profundidad 2, un AND de ORs de literales), se sabe que este problema de "como máximo dos veces" puede resolverse en tiempo polinómico. De hecho, aplicar la "regla de resolución" repetidamente funcionará. Pero no está claro (al menos, no para mí) cómo extender la resolución para la clase de fórmulas generales para obtener un algoritmo de tiempo polinómico. Obsérvese que cuando reducimos una fórmula a la forma normal conjuntiva de la manera habitual, esta reducción introduce variables con tres ocurrencias. Así que parece plausible que tal vez uno podría ser capaz de codificar un $NP$ -completo en la estructura adicional que proporciona una fórmula, aunque sólo tenga dos ocurrencias por variable.

Creo que el problema puede resolverse en tiempo polinómico. Me sorprende mucho no haber encontrado ninguna referencia a este problema en la bibliografía. Tal vez no estoy buscando en los lugares correctos.

ACTUALIZACIÓN: Por favor, piensa en el problema antes de mirar más abajo. La respuesta es sorprendentemente sencilla.

Answer 1

Un teorema en un artículo de Peter Heusch, "The Complexity of the Falsifiability Problem for Pure Implicational Formulas" (MFCS'95), parece sugerir que el problema es NP-duro. Repito aquí la primera parte de su demostración:

Por reducción a partir de la versión restringida de 3SAT en la que cada variable aparece como máximo 3 veces. Dado un CNF, WOLOG cada variable con 3 ocurrencias ocurre una vez positivamente y dos veces negativamente. Si $x$ es una variable de este tipo, sea $C_1$ , $C_2$ sean las cláusulas tales que $C_1 = \neg x \vee C_1'$ y $C_2 = \neg x \vee C_2'$ . Introducir nuevas variables $x'$ y $x''$ y sustituir $C_1$ y $C_2$ por $\neg x \vee (x' \wedge x'')$ , $\neg x' \vee C_1'$ , $\neg x'' \vee C_2'$ . Repite.

Answer 2

He aquí un argumento que sugiere vagamente que este problema debería ser difícil. Supongamos que tengo una puerta $G$ con 6 cables de entrada, $w_1$ , $w_2$ , ..., $w_6$ y 1 cable de salida que da como resultado TRUE si y sólo si:

1. ( $w_1$ O $w_2$ ) Y ( $w_3$ O $w_4$ ) Y ( $w_5$ O $w_6$ )

Y

1. ( $w_1 \neq w_3$ O $w_2 \neq w_4$ ) Y ( $w_1 \neq w_5$ O $w_2 \neq w_6$ ) Y ( $w_3 \neq w_5$ O $w_4 \neq w_6$ ).

Afirmo que es NP-completo determinar si un circuito construido con $G$ y AND es satisfactoria, incluso si cada variable sólo se utiliza dos veces.

Pruebas: Reduzco al problema de 3 bordes coloreables . Para cada arista de mi grafo, tengo dos variables booleanas; para cada vértice, tengo un $G$ -gate, todos esos $G$ puertas se topan con una gran Y. La definición de $G$ dice precisamente que todas mis aristas tienen colores diferentes. Cada variable se utiliza dos veces porque cada arista se encuentra en dos vértices.

Entonces, para probar que el problema de Ryan es polinómico, tenemos que usar alguna diferencia entre las compuertas AND y OR y mi $G$ puerta..

Answer 3

Realmente no tengo una respuesta para ti, pero al menos hay algunas simplificaciones fáciles que puedes realizar:

(1) Si las dos apariciones de una variable tienen el mismo signo (o una variable sólo aparece una vez), también puede establecer el valor que hace que ambas apariciones sean verdaderas.

(2) Supongamos que las dos apariciones de una variable tienen signos opuestos y que los caminos desde ellas hasta su antepasado menos común en el árbol de expresiones están formados sólo por conjunciones. Entonces todos los valores en las expresiones intermedias a lo largo de uno de estos caminos, y en el LCA, deben ser falsos, por lo que también podría reemplazar todo ese subárbol por un literal falso.

(3) Añadido después de ver el ejemplo de Ryan de (x ⋁ y) ⋀ ¬x ⋀ ¬y: supongamos que ambas apariciones de una variable tienen signos opuestos, y uno de los caminos a su ancestro menos común consiste sólo en conjunciones. En ese caso, sería mejor que esa variable fuera verdadera y la otra falsa, porque la configuración opuesta no puede conducir a un valor verdadero en el LCA.

¿Quizá se dé el caso de que cualquier fórmula no trivial que no contenga ninguno de estos patrones sea siempre satisfacible?