El problema de decisión CNF-SAT se puede describir de la siguiente manera:
Entrada: Una fórmula booleana en forma conjuntiva normal.
Pregunta: ¿Existe una asignación variable que satisfaga ?
Estoy considerando varios enfoques diferentes para resolver CNF-SAT con una máquina de Turing de dos cintas no determinista .
Creo que hay una NTM que resuelve CNF-SAT en .
Pregunta: ¿Hay una NTM que resuelva CNF-SAT en pasos ?
Se aprecia cualquier referencia relevante incluso si solo proporcionan enfoques no deterministas de tiempo casi lineal.
time-complexity
sat
turing-machines
np
nondeterminism
Michael Wehar
fuente
fuente
Respuestas:
Este es solo un comentario extendido. Hace algunas veces pregunté (a mí mismo :-) qué tan rápido puede ser un NTM multitapa que acepta un lenguaje NP (razonablemente codificado). Se me ocurrió esta idea:
3-SAT permanece NP-completo incluso si las variables se representan en unario. En particular, podemos convertir una cláusula, supongamos , de una fórmula arbitraria 3-SAT φ en n variables y m cláusulas en una secuencia de caracteres sobre el alfabeto Σ = { + , - , 1 } en el que cada aparición de variable se representa en unario:(xi∨¬xj∨xk) φ n m Σ={+,−,1}
Por ejemplo, se puede convertir a:(x2∨−x3∨+4)
Entonces podemos convertir una fórmula 3-SAT en una cadena equivalente U ( φ i ) concatenando sus cláusulas. El lenguaje L U = { U ( φ i ) ∣ φ i ∈ 3 - S A T } es NP-completo.φi U(φi) LU= { U( φyo) ∣ φyo∈ 3 - SA T}
Una NTM de 2 cintas puede decidir si una cadena en el tiempo 2 | x | De este modo.x ∈ LU 2 | x |
Ejemplo:
El tiempo puede reducirse a si agregamos algunos símbolos redundantes a la representación de la cláusula:El | x |
( marca el final de la fórmula)+++
De esta manera, la segunda cabeza puede volver a la celda más a la izquierda, mientras que la primera escanea la parte . Usando ++ como delimitador de cláusula y +++ como marcador para el final de la fórmula, podemos usar la misma representación para fórmulas CNF con un número arbitrario de literales por cláusula.0 0yo ++ +++
fuente
No es exactamente lo que está buscando, pero para la NTM de 1 cinta, la respuesta parece ser negativa: SAT no se puede resolver con una NTM de 1 cinta en un tiempo lineal no determinista.
Según este documento (Teorema 4.1), la clase de idiomas regulares es exactamente la clase de idiomas reconocidos por una NTM de 1 cinta en el tiempo o ( n log ( n ) ) . Por lo tanto, si existiera un SAT de resolución de NTM de 1 cinta en el tiempo o ( n log ( n ) ) , entonces SAT (más precisamente, el conjunto de fórmulas satisfactorias en CNF) sería un lenguaje regular, por lo tanto solucionable en un espacio constante determinista.R Esol o ( n log( n ) ) o ( n log( n ) )
fuente