Complexidade da versão de pesquisa do 2-SAT assumindo

Se , então há um algoritmo logspace que resolve a versão decisão de 2-sab.$\mathsf{L = NL}$

• É conhecido como implicando que há um algoritmo logspace para obter uma atribuição de satisfazer , quando dado um exemplo satisfatível 2-sab como entrada?$\mathsf{L = NL}$

• Se não, e os algoritmos que usam espaço sub-linear (no número de cláusulas)?

Dado um 2-CNF satisfatório , você pode calcular uma atribuição satisfatória específica e por uma função NL (ou seja, existe um predicado NL P ( ϕ , i ) que informa se e ( x i ) é verdadeiro). Uma maneira de fazer isso é descrita abaixo. Usarei livremente o fato de o NL estar fechado sob A C$\phi$$e$$P(\phi,i)$$e(x_i)$$\mathrm{AC}^0$ -reductions, portanto, NL-funções são fechados sob composição; isso é uma consequência de NL = coNL.

Seja um 2-CNF satisfatório. Para qualquer literal a , deixe a → ser o número de literais alcançáveis ​​de a por um caminho direcionado no gráfico de implicação de ϕ e a ← o número de literais a partir dos quais $\phi(x_1,\dots,x_n)$$a$$a^\to$$a$$\phi$$\let\ot\leftarrow a^\ot$$a$ é alcançável. Ambos são computáveis ​​em NL.

Observe que e ¯ a ← = a → , devido à simetria inclinada do gráfico de implicação. Defina uma atribuição e para que$\let\ob\overline \ob a^\to=a^\ot$$\ob a^\ot=a^\to$$e$

• se , então e ( a ) = 1 ;$a^\ot>a^\to$$e(a)=1$

• se , então e ( a ) = 0 ;$a^\ot<a^\to$$e(a)=0$

• se , deixe i ser mínimo de modo a que x i ou ¯ x i aparece na componente fortemente ligado de uma (isto não pode ser ao mesmo tempo, como φ é satisfatório). Coloque e ( a ) = 1 se x i aparecer e e ( a ) = 0 caso contrário.$a^\ot=a^\to$$i$$x_i$$\ob x_i$$a$$\phi$$e(a)=1$$x_i$$e(a)=0$

A simetria de inclinação do gráfico implica que , portanto, essa é uma atribuição bem definida. Além disso, para qualquer aresta a → b no gráfico de implicação:$e(\ob a)=\ob{e(a)}$$a\to b$

• Se não estiver acessível a partir de b , então a ← < b ← e a → > b → . Assim, e ( a ) = 1 implica e ( b ) = 1 .$a$$b$$a^\ot<b^\ot$$a^\to>b^\to$$e(a)=1$$e(b)=1$

• Caso contrário, e b estão no mesmo componente fortemente ligado, e um ← = b ← , um → = b → . Assim, e ( a ) = e ( b ) .$a$$b$$a^\ot=b^\ot$$a^\to=b^\to$$e(a)=e(b)$

Segue-se que .$e(\phi)=1$