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

Question

(Si conoces los fundamentos de la informática teórica, puedes saltar inmediatamente al cuadro oscuro de abajo. Pensé en tratar de explicar mi pregunta muy cuidadosamente, para maximizar el número de personas que la entiendan).

Decimos que un Fórmula booleana es una fórmula propositiva sobre algunas variables 0-1 $x_1, \ldots ,x_n$ que involucran conecciones AND y OR, donde los átomos son literales que son ejemplos de $x_i$ o $\neg x_i$ para algunos $i$ . Es decir, una fórmula booleana es una fórmula "monótona" sobre la $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 de 0-1 a las variables de una fórmula es satisfactoria si la fórmula evalúa a $1$ en la misión.

El teorema de Cook-Levin dice que el general la satisfacción de las fórmulas booleanas El problema es $NP$ -completo: dada una fórmula arbitraria, es $NP$ - es difícil encontrar un trabajo satisfactorio para él. De hecho, incluso las satisfactorias fórmulas booleanas donde cada variable $x_i$ aparece como máximo tres veces en la fórmula es $NP$ - completo. (Aquí hay una reducción del caso general a este caso: Supongamos que una variable $x$ aparece $k > 3$ veces. Reemplazar cada una de sus ocurrencias con nuevas variables frescas $x^1, x^2, \ldots , x^k$ y limitar estos $k$ variables para que todas tomen el mismo valor, al ANDar 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).$$ El número total de ocurrencias de cada variable $x^j$ es ahora tres.) Por otra parte, si cada variable aparece sólo una vez en la fórmula, entonces el algoritmo de satisfacción es muy fácil: ya que tenemos una fórmula monótona en $x_1, \ldots , x_n, \neg x_1, \ldots , \neg x_n$ nos pusimos $x_i$ a $0$ si $\neg x_i$ aparece, 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$ -completo, o solucionable en tiempo de polinomio?

Para aclarar más, aquí hay 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))$$

Nótese que cuando restringimos la clase de fórmulas más a la forma normal conjuntiva (es decir, un circuito de profundidad-2, un Y de O de literales) entonces este problema de "a lo sumo dos veces" se sabe que es solucionable en tiempo polinómico. De hecho, la aplicación de 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 politono. 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. Por lo tanto, parece plausible que tal vez se pueda codificar un $NP$ -problema completo en la estructura adicional proporcionada por una fórmula, incluso una con sólo dos ocurrencias por variable.

Creo que el problema es que el tiempo de polinomios es solucionable. Estoy muy sorprendido de no haber encontrado una referencia a este problema en la literatura. Tal vez no estoy buscando en los lugares correctos.

ACTUALIZACIÓN: Por favor, piense en el problema antes de mirar abajo. La respuesta es sorprendentemente simple.

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 de este tipo, WOLOG cada variable con 3 ocurrencias ocurre una vez positivamente y dos veces negativamente. Si $x$ es una variable de este tipo, dejemos que $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 reemplazar $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

Este es 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 satisfacible, incluso si cada variable se utiliza sólo dos veces.

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

Por lo tanto, para demostrar que el problema de Ryan es polinómico, tenemos que utilizar alguna diferencia entre las puertas AND y OR y mi $G$ puerta..

Answer 3

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

(1) Si las dos apariciones de una variable tienen el mismo signo (o una variable aparece sólo una vez), es mejor ponerle 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 antecesor 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, es mejor establecer que esa ocurrencia de la variable sea verdadera y la otra falsa, porque la configuración opuesta no puede conducir a un valor verdadero en el LCA.

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