Каковы наилучшие текущие нижние границы на 3SAT?

Ответы:

43

Насколько я знаю, наиболее известная «независимая от модели» нижняя граница времени для SAT является следующей. Пусть и S будут временем и пространственным пределом любого алгоритма SAT. Тогда мы должны бесконечно часто T S n 2 cos ( π / 7 ) - o ( 1 ) . Примечание 2 cos ( π / 7 ) 1.801 . (Результат, на который ссылается Суреш, немного устарел.) Этот результат появился в STACS 2010, но это расширенный реферат гораздо более длинной статьи, которую вы можете получить здесь:TSTSN2соз(π/7)-о(1)2соз(π/7)1,801http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf

Конечно, вышеупомянутая работа основывается на многих предыдущих работах, которые упоминаются в блоге Липтона (см. Ответ Суреша). Кроме того, когда пространственная граница S приближается к n, нижняя граница времени T также приближается к n. Вы можете доказать лучший «пространственно-временной компромисс» в этом режиме; см. обзор Дитером ван Мелкебеком нижних границ пространственно-временного пространства SAT за 2008 год.

Если вы ограничиваете себя многолучевыми машинами Тьюринга, вы можете доказать бесконечно часто. Это было доказано Рахулом Сантанамом и следует из аналогичной нижней границы, известной для PALINDROMES в этой модели. Мы полагаем, что вы сможете доказать квадратичную нижнюю границу, которая «не зависит от модели», но которая была неуловимой в течение некоторого времени.TSN2-о(1)

Для неоднородных цепей с ограниченным разветвлением, я не знаю никакой нижней границы глубины лучше, чем .журналN

Райан Уильямс
источник
2
мы работаем над этим. Смотрите эту ссылку: meta.cstheory.stackexchange.com/questions/3/latex-math-support
Суреш Венкат
2
@vinayak: Утверждение, в котором «бесконечно часто» появляется в приведенном выше, является отрицанием: «Существует алгоритм SAT, такой что , почти везде». Отрицание «почти везде» - «бесконечно часто», это означает, что для каждого алгоритма существует бесконечно много случаев, когда он не может решить экземпляр с небольшим произведением времени и пространства. TSN2соз(π/7)+о(1)
Райан Уильямс
2
Удивительно, что у нас есть более низкие нижние оценки на для действительно простой проблемы отличимости элементов ( T S = Ω ( n 2 - o ( 1 ) ) по Яо), чем для SAT! TSTS=Ω(N2-о(1))
Уоррен Шуди
2
@ Уоррен, не совсем, насколько я знаю. Нижние границы, такие как Yao, относятся к модели программы ветвления на основе сравнения , которая не столь выразительна, как универсальная машина произвольного доступа. Можно представить решение проблемы отличимости элементов без каких-либо прямых сравнений между элементами вообще.
Райан Уильямс
1
@ Turbo - лучшая нижняя граница для 3sat с линейно множественными предложениями такая же, как я написал, потому что сокращение от sat до 3sat чрезвычайно локально. Чтение литературы по теме также покажет это.
Райан Уильямс
17

о(N)Nсс3

Суреш Венкат
источник
1
Nо(1)о(N)
11

Ω(Nс)с>1

Лев Рейзин
источник
4

Мое понимание такое же, как у Льва Рейзина. Возможно, что существует детерминированный полный алгоритм для SAT, который работает в пространстве O (n) и во времени O (n). Удивительно, что существование такого эффективного алгоритма не запрещено.

Джорджо Камерани
источник