¿SAT es un lenguaje sin contexto?

Estoy considerando el lenguaje de todas las fórmulas lógicas proposicionales satisfactorias, SAT (para asegurarnos de que tenga un alfabeto finito, codificaríamos las letras proposicionales de alguna manera adecuada [editar: las respuestas señalaron que la respuesta a la pregunta puede no ser sólida bajo codificaciones variables, por lo que uno debe ser más específico; consulte mis conclusiones a continuación] ). Mi simple pregunta es

¿ SAT es un lenguaje sin contexto?

Mi primera suposición fue que la respuesta de hoy (principios de 2017) debería ser "Nadie lo sabe, ya que esto se relaciona con preguntas no resueltas en la teoría de la complejidad". Sin embargo, esto no es realmente cierto (ver la respuesta a continuación), aunque tampoco es completamente falso. Aquí hay un breve resumen de las cosas que sabemos (comenzando con algunas cosas obvias).

SAT no es regular (porque incluso la sintaxis de la lógica proposicional no es regular, debido a paréntesis coincidentes)
SAT es sensible al contexto (no es difícil dar un LBA para ello)
SAT es NP-completo (Cook / Levin), y en particular decidido por TM no deterministas en tiempo polinomial.
SAT también puede ser reconocido por autómatas de pila no deterministas unidireccionales (1-NSA) (ver Rondas WC, Complejidad de reconocimiento en lenguajes de nivel intermedio , Teoría de conmutación y autómatas, 1973, 145-158 http://dx.doi.org/ 10.1109 / SWAT.1973.5 )
El problema verbal para los lenguajes sin contexto tiene su propia clase de complejidad (ver https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cfl ) $\textbf{CFL}$
, donde es la clase de problemas de espacio de registro reducible a (consultehttps://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#logcfl). Se sabe que . $\textbf{CFL}\subseteq\textbf{LOGCFL}\subseteq\textbf{AC}^{\textbf{1}}$ $\textbf{LOGCFL}$ $\textbf{CFL}$ $\textbf{NL}\subseteq\textbf{LOGCFL}$
$\textbf{NL}\subsetneq\textbf{NP}$ $\textbf{NL}=\textbf{NP}$ $\textbf{NC}^{\textbf{1}}\subsetneq\textbf{PH}$ $\textbf{NP}$ $\textbf{LOGCFL}$ $\textbf{LOGCFL}$

Sin embargo, este último punto todavía deja la posibilidad de que se sepa que SAT no está en . En general, no pude encontrar mucho sobre la relación de con la jerarquía que podría ayudar a aclarar el estado epistémico de mi pregunta. $\textbf{CFL}$ $\textbf{CFL}$ $\textbf{NC}$

Observación (después de ver algunas respuestas iniciales): no espero que la fórmula esté en forma conjuntiva normal (esto no hará una diferencia en la esencia de la respuesta, y generalmente los argumentos aún se aplican ya que un CNF también es una fórmula. Pero afirme que la versión del número de variables constantes del problema es regular falla, ya que uno necesita paréntesis para la sintaxis).

Conclusión: Contrariamente a mi suposición inspirada en la teoría de la complejidad, uno puede mostrar directamente que SAT no está libre de contexto. La situación por lo tanto es:

Se sabe que SAT no está libre de contexto (en otras palabras: SAT no está en ), bajo el supuesto de que uno usa una codificación "directa" de fórmulas donde las variables proposicionales se identifican por números binarios (y algunos otros símbolos se utilizan para operadores y separadores). $\textbf{CFL}$
No se sabe si SAT está en , pero "la mayoría de los expertos piensan" que no lo está, ya que esto implicaría . Esto también significa que se desconoce si otras codificaciones "razonables" de SAT están libres de contexto (suponiendo que consideremos que el espacio de registro es un esfuerzo de codificación aceptable para un problema NP-difícil). $\textbf{LOGCFL}$ $\textbf{P}=\textbf{NP}$

Tenga en cuenta que estos dos puntos no implican . Esto se puede mostrar directamente al mostrar que hay idiomas en (por lo tanto, en ) que no están libres de contexto (por ejemplo, ). $\textbf{CFL}\subsetneq\textbf{LOGCFL}$ $\textbf{L}$ $\textbf{LOGCFL}$ $a^nb^nc^n$

cc.complexity-theory circuit-complexity sat context-free mak
fuente

Si lo fuera, entonces P = NP.

Ryan

Si SAT no tuviera contexto, entonces la programación dinámica (el algoritmo CYK) daría un algoritmo de tiempo polinómico para probar la membresía en SAT, dando P = NP. Incluso P = NP no significaría que los SAT estuvieran libres de contexto. Parece que esta codificación de variables podría ser más importante de lo que le estás dando crédito. No he resuelto los detalles, pero si agregaste "subíndices" unarios o binarios a las variables, creo que tendrías problemas para distinguir (x e y) de (x y no x) para índices lo suficientemente grandes.

AdamF

Debe ser preciso acerca de la representación antes de reclamar conclusiones P = NP. Por ejemplo, factorizar un número N es tiempo polinomial en N (la pregunta interesante es sobre el número de bits necesarios para escribir N en binario, o sobre log N).

Aryeh

Era consciente de la conclusión de P = NP y que, por lo tanto, no se esperaba que la respuesta fuera "sí" (perdón por ser un poco provocativo en la forma en que redacté esto ;-). Todavía me preguntaba si esto es realmente conocido o simplemente algo que "la mayoría de los expertos creen" (las respuestas ahora indican claramente que lo primero es cierto; seleccionaré una a su debido tiempo).

mak

Respuestas:

Solo una prueba alternativa con una mezcla de resultados bien conocidos

Suponer que:

Las variables se expresan con la expresión regular $d = (+|-)1(0|1)^*$
y que el lenguaje ( regular ) (sobre utilizado para representar las fórmulas CNF es: ; solo tenga en cuenta que toma todas las fórmulas CNF válidas hasta el cambio de nombre variable. $\Sigma = \{0,1,+,-,\land,\lor\})$ $S = \{ d^+ (\lor d^+)^*(\land (d^+ (\lor d^+)^*))^* \}$ $S$

Por ejemplo, se escribe como: (el operador tiene prioridad sobre ) . $\varphi = (x_1 \lor x_2) \land -x_3$ $s_{\varphi} = +1 \lor +10 \land -11 \in S$ $\lor$ $\land$

Suponga que st la fórmula correspondiente es satisfactoria es CF. $L = \{ s_{\varphi} \in S \, \mid$ $\varphi$ $\}$

Si lo intersectamos con el lenguaje regular: todavía obtenemos un lenguaje CF. También podemos aplicar el homomorfismo: , y el lenguaje sigue siendo CF. $R = \{ +1^a \land -1^b \land -1^c \mid a,b,c > 0 \}$ $h(+) = \epsilon$ $h(-) = \epsilon$

Pero el lenguaje que obtenemos es: , porque si entonces la fórmula "fuente" es que es insatisfactorio (de manera similar si ). Pero es una conocida contradicción de lenguaje no CF . $L' = \{ 1^a \land 1^b \land 1^c \mid a \neq b, a \neq c\}$ $a=b$ $+x_a \land -x_a \land -x_b$ $a=c$ $L'$ $\Rightarrow$

Marzio De Biasi
fuente

Acepté esta respuesta ahora, ya que todavía hay un problema abierto con el otro enfoque (ver comentarios) y me gusta el argumento algo más básico. Puede ser bueno enfatizar que el argumento es específico de la codificación elegida y, de hecho, se desconoce si uno podría encontrar otra codificación simple (espacio de registro) que conduzca a un lenguaje sin contexto.

mak

@mak: sospecho que cualquier otra codificación "razonable" de SAT puede probarse que no es CF con una técnica similar. Quizás otra dirección interesante sería estudiar si podemos aplicar algún tipo de diagonalización para obtener una prueba más general: la fórmula SAT codifica un cálculo que simula un autómata de empuje en una entrada dada y es satisfactoria si y solo si no lo hace. No lo aceptes. Pero es solo una idea borrosa ...

Marzio De Biasi

Comprobando si una cadena está en un idioma normal está en P. Suponga que SAT estaba en Reg. Entonces NP = coNP. Deje L estar en Reg. Considere la fórmula que es verdadera si no está en L. Está en NP, por lo que puede expresarse como una fórmula SAT. Está en el idioma si no es así.

Kaveh

Si el número de variables es finito, también lo es el número de conjunciones satisfactorias, por lo que su lenguaje SAT es finito (y, por lo tanto, regular). [Editar: este reclamo asume el formulario CNFSAT.]

De lo contrario, aceptemos codificar fórmulas como por . Usaremos el lema de Ogden para demostrar que el lenguaje de todas las conjunciones satisfactorias no está libre de contexto. $(x_{17}\vee \neg x_{21})\wedge (x_{1}\vee x_{2}\vee x_3)$ $(17+\tilde{} 21)(1+2+3)$

Sea la constante de "marcado" en el lema de Ogden, y considere una fórmula sat cuya primera cláusula consiste en , es decir, la codificación de , donde es el número decimal que consiste en unos. Marcamos los unos de y luego exigimos que todos los bombeos de la descomposición apropiada de (ver la conclusión del lema de Ogden) también sean satisfactorios. Pero podemos bloquear esto fácilmente al no requerir ninguna cláusula que contenga , donde es una secuencia de más corta que $p$ $w$ $(1^p)$ $(x_N)$ $N$ $p$ $p$ $1^p$ $w$ $x_q$ $q$ $1$ $p$ , ser satisfactoria, por ejemplo, asegurando que cualquier otra cláusula de tenga una negación de cada . Esto significa que falla la propiedad de "bombeo negativo" y concluimos que el lenguaje no está libre de contexto. [Nota: ignoré los casos triviales en los que el bombeo produce cuerdas mal formadas.] $w$ $x_q$ $w$

Aria
fuente

Nota: En mi afirmación de que, para un número finito de variables, el lenguaje es finito, implícitamente rechazo repetir una variable dentro de una cláusula o una cláusula sin límites muchas veces

Aryeh

... Pero creo que el lenguaje sigue siendo regular, porque uno toma la colección finita de fórmulas "esencialmente distintas" (es decir, sin repeticiones triviales) y luego permite las diversas repeticiones.

Aryeh

El reclamo con regularidad solo funciona para CNFSAT (agregué una aclaración a mi pregunta).

mak

Incluso con fórmulas arbitrarias que no son CNF en finitas variables, la satisfacción (y cualquier lenguaje que no pueda distinguir dos fórmulas lógicamente equivalentes para el caso) se ve fácilmente sin contexto. Sin embargo, no veo la relevancia de esto. La satisfacción de las fórmulas en muchas variables finitas es un problema trivial que no tiene nada que ver con la complejidad del SAT.

Emil Jeřábek

Bien, veo el problema: estaba suponiendo implícitamente quepuede limitarse en longitud (como en el clásico lema de bombeo), al tiempo que puede especificar algo sobre su ubicación en la cadena. Creo que el argumento se puede solucionar volviendo a hacer el lema de bombeo desde cero. Haremos que la primera variable sea una secuencia realmente larga de 1, lo suficientemente larga como para que algún subárbol que genere una subcadena contigua de esos 1 tenga que ser lo suficientemente profundo como para que se aplique el principio de pidgeonhole.

| x y z |

$|xyz|$

Aryeh