Сложность поиска версии 2-SAT при условии

Если , то существует алгоритм пространства журнала, который решает версию решения 2-SAT.$\mathsf{L = NL}$

• Известно ли, что подразумевает наличие алгоритма логического пространства для получения удовлетворительного назначения , когда в качестве входных данных предоставляется удовлетворительный экземпляр 2-SAT?$\mathsf{L = NL}$

• Если нет, то как насчет алгоритмов, которые используют сублинейное пространство (в количестве пунктов)?

Учитывая выполнимое 2-CNF , вы можете вычислить конкретное удовлетворяющее назначение e с помощью NL-функции (то есть существует предикат NL P ( ϕ , i ), который сообщает вам, верно ли e ( x i ) ). Один из способов сделать это описан ниже. Я буду свободно использовать тот факт, что NL замкнут относительно A C 0 -редукций, поэтому NL-функции замкнуты относительно композиции; это является следствием NL = coNL.$\phi$$e$$P(\phi,i)$$e(x_i)$$\mathrm{AC}^0$

Пусть выполнимая 2-CNF. Для любого литерала a , пусть a → будет числом литералов, достижимых из a по направленному пути в графе импликации ϕ , и a ← числом литералов, из которых достижим a . Оба вычислимы в NL.$\phi(x_1,\dots,x_n)$$a$$a^\to$$a$$\phi$$\let\ot\leftarrow a^\ot$$a$

Заметим , что и ¯ ← = → , из - за кососимметричности импликации графа. Определите назначение e так, чтобы$\let\ob\overline \ob a^\to=a^\ot$$\ob a^\ot=a^\to$$e$

• если , то e ( a ) = 1 ;$a^\ot>a^\to$$e(a)=1$

• если , то e ( a ) = 0 ;$a^\ot<a^\to$$e(a)=0$

• если ← = → , пусть я быть минимальным , так что х I или ¯ х я появляюсь в сильно связной компоненте (он не может быть одновременно, так как φ выполнима). Положите e ( a ) = 1, если появляется x i , и e ( a ) = 0 в противном случае.$a^\ot=a^\to$$i$$x_i$$\ob x_i$$a$$\phi$$e(a)=1$$x_i$$e(a)=0$

Кососимметричность графы следует , что , следовательно , это четко определенное назначение. Более того, для любого ребра a → b в графе импликации:$e(\ob a)=\ob{e(a)}$$a\to b$

• Если не достижимо от b , то a ← < b ← и a → > b → . Таким образом, e ( a ) = 1 влечет e ( b ) = 1 .$a$$b$$a^\ot<b^\ot$$a^\to>b^\to$$e(a)=1$$e(b)=1$

• В противном случае и b находятся в одной и той же сильно связной компоненте, а a ← = b ← , a → = b → . Таким образом, e ( a ) = e ( b ) .$a$$b$$a^\ot=b^\ot$$a^\to=b^\to$$e(a)=e(b)$

Отсюда следует, что .$e(\phi)=1$