Complejidad de la versión de búsqueda de 2-SAT asumiendo que

Si , entonces hay un algoritmo de espacio de registro que resuelve la versión de decisión de 2-SAT.$\mathsf{L = NL}$

• ¿Se sabe que implica que hay un algoritmo de espacio de registro para obtener una asignación satisfactoria , cuando se le da una instancia satisfactoria de 2-SAT como entrada?$\mathsf{L = NL}$

• Si no, ¿qué pasa con los algoritmos que usan espacio sub-lineal (en el número de cláusulas)?

Dado un 2-CNF satisfactorio $\phi$ , puede calcular una asignación satisfactoria particular $e$ mediante una función NL (es decir, hay un predicado NL $P(\phi,i)$ que le dice si $e(x_i)$ es verdadero). Una forma de hacerlo se describe a continuación. Usaré libremente el hecho de que NL está cerrado bajo reducciones $\mathrm{AC}^0$ , por lo tanto, las funciones NL están cerradas bajo composición; Esto es una consecuencia de NL = coNL.

Sea $\phi(x_1,\dots,x_n)$ un 2-CNF satisfactoria. Para cualquier literal $a$ , vamos a $a^\to$ ser el número de literales accesible desde $a$ por un camino dirigido en el gráfico implicación de $\phi$ , y el número de literales de la que es alcanzable. Ambos son computables en NL.$\let\ot\leftarrow a^\ot$$a$

Observe que , y , debido a la simetría sesgada del gráfico de implicación. Definir una tarea para que ¯ a ←=a→$\let\ob\overline \ob a^\to=a^\ot$$\ob a^\ot=a^\to$$e$

• si , entonces ; e ( a ) = $a^\ot>a^\to$$e(a)=1$

• si , entonces ; e ( a ) = $a^\ot<a^\to$$e(a)=0$

• si , sea mínimo para que u aparezca en el componente fuertemente conectado de (no puede ser ambos, ya que es satisfactoria). Ponga si aparece , y caso contrario. i x i ¯ x i a ϕ e ( a ) = 1 x i e ( a ) = $a^\ot=a^\to$$i$$x_i$$\ob x_i$$a$$\phi$$e(a)=1$$x_i$$e(a)=0$

La simetría sesgada de la gráfica implica que , por lo tanto, esta es una asignación bien definida. Además, para cualquier borde en el gráfico de implicación: a → $e(\ob a)=\ob{e(a)}$$a\to b$

• Si no se puede acceder desde , entonces , y . Por lo tanto, implica .b a ← < b ← a → > b → e ( a ) = 1 e ( b ) = $a$$b$$a^\ot<b^\ot$$a^\to>b^\to$$e(a)=1$$e(b)=1$

• De lo contrario, y están en el mismo componente fuertemente conectado, y , . Por lo tanto, .b a ← = b ← a → = b → e ( a ) = e ( b $a$$b$$a^\ot=b^\ot$$a^\to=b^\to$$e(a)=e(b)$

Se deduce que .$e(\phi)=1$