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

15

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

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

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

Ниль де Бодрап
источник

Ответы:

16

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

Пусть выполнимая 2-CNF. Для любого литерала a , пусть a будет числом литералов, достижимых из a по направленному пути в графе импликации ϕ , и a числом литералов, из которых достижим a . Оба вычислимы в NL.ϕ(x1,,xn)aaaϕaa

Заметим , что и ¯ = , из - за кососимметричности импликации графа. Определите назначение e так, чтобыa¯=aa¯=ae

  • если , то e ( a ) = 1 ;a>ae(a)=1

  • если , то e ( a ) = 0 ;a<ae(a)=0

  • если = , пусть я быть минимальным , так что х I или ¯ х я появляюсь в сильно связной компоненте (он не может быть одновременно, так как φ выполнима). Положите e ( a ) = 1, если появляется x i , и e ( a ) = 0 в противном случае.a=aixix¯iaϕe(a)=1xie(a)=0

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

  • Если не достижимо от b , то a < b и a > b . Таким образом, e ( a ) = 1 влечет e ( b ) = 1 .aba<ba>be(a)=1e(b)=1

  • В противном случае и b находятся в одной и той же сильно связной компоненте, а a = b , a = b . Таким образом, e ( a ) = e ( b ) .aba=ba=be(a)=e(b)

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

Эмиль Йержабек поддерживает Монику
источник
Это приятно! Есть ли ссылка?
Райан Уильямс
2
Я только что приготовил это, так что я не знаю, но это выглядит достаточно легко для кого-то, чтобы наблюдать это раньше. Мое вдохновение было аргументом, что топологическая сортировка частичных заказов может быть сделана в TC ^ 0, следовательно ts ациклических графов в NL; Это положительно, но в данный момент я не нахожусь в офисе, поэтому мне трудно это искать.
Эмиль Йержабек поддерживает Монику
1
Результат того, что удовлетворяющие назначения могут быть вычислены в FNL, появляется с другим аргументом в Cook, Kolokolova: теория второго порядка для NL, и с немного большим количеством деталей в Cook, Nguyen: логические основы сложности доказательства. Однако, признаюсь, я не могу понять, как это должно работать. Насколько я могу судить, свойство (307), оставленное в качестве упражнения для читателя в книге C & N, просто ложно.
Эмиль Йержабек поддерживает Монику