Está encontrando una solución a un sistema de las ecuaciones de 2SAT separadas por o (formulario DNF) en NP

Question

Quiero saber si encontrar una solución a un número específico de ecuaciones de 2SAT separtidas por o puerta (formulario DNF como a continuación) está en P o NP.

La ecuación tiene variables N total y y cada cláusula es una ecuación 2SAT en sí misma en un subconjunto de variables de 1 a n. Ejemplo:

f= [(x1 || x2) && (! x2 || x3) && (x3 || x4)] ||[(x2 || x5) && (x3 || x6) && (! x4 ||! x6)] ||....

La ecuación F es una DNF de las ecuaciones de 2SAT, que ha dicho las cláusulas M.¿Está encontrando una solución a esto en NP?Si es así, ¿cómo?

También, específicamente, también quiero saber si encontrar falsas instancias de la ecuación F está en P o NP también.

Answer 1

• Primero, permítanme nota de que el título de la pregunta es un poco engañoso, porque $ P $ es un subconjunto de $ NP $ . Vea también el comentario de Yuval Filmus. Supongo lo que usted está pensado para preguntar es si está en $ P $ o en $ np \ SetMinus P $ .
• Además, el nombre "DNF" se refiere específicamente a una disyunción de elemental conjunciones, no una disyunción de las funciones arbitrarias. Lo que está describiendo no es un DNF, sino una disyunción de los CNF.

con eso fuera del camino, aquí está mi respuesta.

---

1. Para satisfacer una disyunción de 2-CNF, todo lo que necesita es satisfacer uno de ellos. Por lo tanto, si aplica el algoritmo de 2 SAT al primero de los CNF y obtiene un "Sí", entonces la respuesta a todo el problema es "Sí". De lo contrario, simplemente sigues adelante al segundo, y así sucesivamente. No debe tomar mucho tiempo, ya que solo lo tiene M de ellos. Si ninguno de ellos se puede satisfacer individualmente, es decir, todos son ceros constantes, entonces, obviamente, todo lo que es un cero constante.

   Entonces, la respuesta a la primera parte es: El problema está en P, con el siguiente algoritmo de decisión:

   Para cada 2-CNF, aplique el algoritmo "normal" 2-SAT (la regla de resolución) para determinar si es satisfactorio o no. Si "SÍ", simplemente vuelva "Sí". Si pasó por todos ellos sin encontrar un "Sí", luego regresa "No".

---

2. Ahora, encontrar los casos "falsos" de esa fórmula (también conocida como el problema de la tautología) es otra pregunta por completo. Por un lado, la tautología para las ORS de AS de ORS es equivalente a la satisfacción de los AISS de ANDS, por el gobierno de De Morgan. Pero eso es solo un caso más general de un problema de SAT ya general, ¿no es así?

   Considere lo que sucede cuando restringe el conjunto de fórmulas posibles para aquellos en las que cada disyunción de dos elementos es realmente solo un elemento, se repite. Así que es una fórmula como $$ F= [(x_1 \ vee x_1) \ & (\ net x_2 \ vee \ neg x_2) \ & (x_3 \ vee x_3)] \ vee [(x_2 \ vee x_2) \ & (x_4 \ vee x_4) \ & ( x_5 \ vee x_5)] \ vee ... $$ que es equivalente a $$ F= [x_1 \ & \ net x_2 \ & x_3] \ vee [x_2 \ & x_4 \ & x_5] \ vee ... $$ que es solo un DNF normal. Después de la transformación de De Morgan, obtienes un CNF normal, cuya satisfacción se sabe que es NP-HARD. Por lo tanto, cualquier problema que incluya este como subconjunto también será al menos NP-HARD.

   Obviamente, el problema en la pregunta no será fuera NP, ya que aún es polinomialmente verificable. Así que la respuesta a su segunda pregunta es "en NP, pero no en P".