La prueba de Sipser de NP-completeness de SAT

Question

Sólo necesito un poco de ayuda con el Cocinero-Levin teorema (SAT es NP-completo). La prueba de este teorema no es tan claro para mí. Yo uso Sipser del libro "Introducción a la Teoría de la Computación". A esta prueba, todo lo demás parece muy claro y evidente; por lo tanto elegí este libro. La prueba está en la página 277.

Yo no puede entender el concepto de tableau desde el principio .

En particular,

1. cada fila en la tabla presenta la rama con los estados si los nodos correspondientes TM?

2. ¿cuál es la idea de la ventana representa ?

Puede ser que hay alguna versión simplificada, que usted sepa?

Gracias!

---

Gracias por la gran explicación!

Me gustaría hacerle algunas preguntas más

la idea de tableau es claro

la idea de celular es de claro

pero todavía tengo un problema con el diseño de $\phi$ (corresponden expresión booleana a la entrada de $\omega$)

Ahora diseñamos $\phi$, de modo que un satisfing asignación a las variables no corresponde a una aceptación de tableau para N en $\omega$. La fórmula para $\phi$ es el Y de cuatro piezas de $\phi_{cell}\wedge\phi_{start}\wedge\phi_{move}\wedge\phi_{accept} $ (¿cómo puede esta construcción describen $\phi$?) . Se describe cada parte.

Como hemos mencionado anteriormente, tunrning variable $x_{i,j,s}$, corresponde a la colocación de símbolo $s$ $cell[i,j]$ La primera cosa que debe garantizar, en orden a obtener una correspondencia entre una tarea y un tableau es que la asignación de turnos en exactamente una variable para cada celda. Fórmula $\phi_{cell}$ asegura que este requerimiento, expresándola en términos de operaciones Booleanas

$$\phi_{cell} = \underset{1\leqslant i, j\leqslant n^{k}}{\wedge }\left [ \left ( \underset {s\epsilon C}{\wedge} x_{x,j,s} \right ) \wedge \left (\underset{\underset{s\neq t}{s,t\epsilon C}}{\wedge} \left ( \overline{x_{i,j,s}} \vee \overline{x_{i,j,t}} \right ) \right ) \right ]$$

Por qué $\phi_{cell}$ tiene una ecuación anterior?

Gracias!

Answer 1

Estoy usando una segunda respuesta para responder a sus recién agregado pregunta. Se hizo un pequeño error, la fórmula de la celda debe ser el siguiente:

$$\phi_{cell} = \underset{1\leqslant i, j\leqslant n^{k}}{\wedge }\left [ \left ( \underset {s\epsilon C}{\vee} x_{i,j,s} \right ) \wedge \left (\underset{\underset{s\neq t}{s,t\epsilon C}}{\wedge} \left ( \overline{x_{i,j,s}} \vee \overline{x_{i,j,t}} \right ) \right ) \right ]$$

Como usted dijo, la variable $x_{i,j,s}$ representa el símbolo s en la celda[i,j], por lo que debe ser verdadera si y sólo si la celda[i,j] contiene el símbolo $s$. Vamos a analizar la fórmula de la celda correctamente. Existe cabo de 3 partes:

• $\Large\underset {s\epsilon C}{\vee} x_{i,j,s}$ dice que para cada uno de ellos fijo $i$ $j$ debe haber al menos un símbolo de $s$ en la celda[i,j].
• $\large\underset{\underset{s\neq t}{s,t\epsilon C}}{\wedge} \left ( \overline{x_{i,j,s}} \vee \overline{x_{i,j,t}} \right )$ dice que, para cada par distinto de los símbolos $s$ y $t$: $\large x_{i,j,s}$ y $\large x_{i,j,t}$ no pueden ser ambas verdaderas al mismo tiempo. Esto representa que una célula no puede tener más de un símbolo.

La combinación de ambos puntos nos dice que para cada uno de ellos fijo $i$ $j$ no tiene que ser exactamente un símbolo de $s$ ( NO MÁS Y NO MENOS), de modo que la variable $x_{i,j,s} = 1$. De manera más intuitiva que nos dice que cada celda sólo puede contener exactamente un símbolo.

Ahora lo único que queda es analizar es el $\large\underset{1\leqslant i, j\leqslant n^{k}}{\wedge }$ parte la encapsulación de las partes ya hemos analizado. Claramente a esta parte nos dice que la fórmula tiene que llevar a cabo para cada celda en el tableau.

Espero que esto ayudó.

Answer 2

El cuadro representa la máquina de turing a su cálculo. Cada fila en el tableau es una instantánea de la máquina de Turing su cálculo. Creo que Sipser llama a esta configuración. Esta configuración contiene la máquina de Turing del contenido de las cintas, la posición actual de la cinta y el estado actual de la máquina de Turing.

Ahora, un conjunto de tableau representa un cálculo de una máquina de Turing, donde la primera fila en el tableau es el punto de partida de configuración que contiene el inicio y la de entrada. La última fila de un tableau es un rechazo de configuración o una aceptación de configuración.

Una máquina de Turing determinista sólo tiene un tableau para cada entrada, ya que el cálculo es determinista. Una máquina de Turing no determinista puede tener varios cuadros vivos para una sola entrada, cada uno representando una rama en la máquina no determinista de la computación.

Para explicar la ventana en un cuadro, usted necesita pensar de la máquina de Turing que la transición de la función. En cada paso de la máquina de Turing se hace, se lee un símbolo, mueve su cabeza de la cinta y escribe un símbolo, por lo tanto para un tableau para ser correcta, cada ventana tiene que ser la correcta de acuerdo a la transición de la función. La razón por la ventana contiene 6 celdas, es porque el cálculo de una máquina de Turing es muy locales. Con muy local, nos referimos a que sólo puede tener el efecto de una pocas células en cada paso computacional. Claramente, si se examina la transición de la función, usted va a ver que se puede solo efecto de la celda donde se encuentra actualmente, y la celda a la izquierda o a la derecha.

Para hacer corta una historia larga: El cuadro representa la máquina de Turing de la computación, donde cada fila representa un paso en la máquina de Turing. Obviamente, para asegurarse de que el cálculo es correcto, usted tiene que comprobar cada ventana de acuerdo a la transición de la función, de lo contrario el tableau no representan una máquina de Turing su computacional pasos.

Ahora, la razón por la que uso el tableau es: si hay un cuadro con una aceptación de configuración como su última fila, la máquina de Turing acepta la entrada en el punto de partida de la configuración de tableau. A continuación, se observa que se puede encontrar un SAT fórmula que imita este cuadro. Por tanto, se ha encontrado una fórmula que es válido si y sólo si la máquina de Turing acepta la entrada dada.