¿Decidir un problema: es en $NP$, $NPC$ o $P$?

Question

Me gustaría su ayuda con la comprensión de si el problema siguiente es en $P$, $NP$, $NPC$.

El problema $B$:

Entrada: $3CNF$ fórmula que contiene más de una cláusula.

salida: Podemos dividir la fórmula para dos $3CNF$ conste que las cláusulas?

Realmente me gustaría aprender a analizar este tipo de preguntas.

Primero sé que con el fin de que el problema estaría en $NP$ necesito encontrar un polinomio verificador para el problema, por lo que puedo comprobar todas las opciones de particiones y ver si se satisface el problema. así que el problema está probablemente en $NP$, con el fin de saber si es completa, necesito encontrar a una reducción de un NP-duro problema, primero que vino a mi cabeza es $3SAT$, pero, ¿cómo una adecuada reducción sería así? o tal vez es simplemente en $P$? ¿cuál es el camino para decidir esto?

Agradecería algunas explicaciones.

Muchas gracias!

Answer 1

El siguiente programa resuelve el problema de $B$ constante de tiempo:

Input B.
Output "yes".

A ver que "sí" es siempre la respuesta correcta, tener en cuenta que podemos dividir la entrada en un conjunto de cláusula donde cada cláusula contiene al menos un literal positivo, y otro conjunto donde cada cláusula contiene al menos un literal negativo. El primer conjunto puede ser satisfecho por hacer todo lo verdadero; el segundo puede ser satisfecho por hacer todo lo falso.

(En el caso especial en donde uno de los sistemas que acabamos de describir está vacía, el original 3CNF fórmula debe ser válido, y así cualquier partición que se va a trabajar).

---

La solución anterior, se asume que usted puede mezclar y combinar entre las cláusulas de la entrada. Si usted debe conservar el orden de las cláusulas y solo hay que dividir la inicial 3CNF en un "front end" y "back-end", entonces el problema es NP-completo, por la reducción de 3SAT sí mismo: Dado cualquier 3CNF fórmula, elegir un fresco de la variable $x$ y anexar los dos cláusulas $x\lor x\lor x$$\bar x\lor \bar x\lor \bar x$. La única manera de dividir el extendido fórmula en conste que partes se divide entre las nuevas cláusulas, lo que significa que la extensión de la fórmula es en $B$ exactamente si el original fue válido.