Каковы лучшие нижние границы тока для времени и глубины цепи для 3SAT?
источник
Каковы лучшие нижние границы тока для времени и глубины цепи для 3SAT?
Насколько я знаю, наиболее известная «независимая от модели» нижняя граница времени для SAT является следующей. Пусть и S будут временем и пространственным пределом любого алгоритма SAT. Тогда мы должны бесконечно часто T ⋅ S ≥ n 2 cos ( π / 7 ) - o ( 1 ) . Примечание 2 cos ( π / 7 ) ≈ 1.801 . (Результат, на который ссылается Суреш, немного устарел.) Этот результат появился в STACS 2010, но это расширенный реферат гораздо более длинной статьи, которую вы можете получить здесь:http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf
Конечно, вышеупомянутая работа основывается на многих предыдущих работах, которые упоминаются в блоге Липтона (см. Ответ Суреша). Кроме того, когда пространственная граница S приближается к n, нижняя граница времени T также приближается к n. Вы можете доказать лучший «пространственно-временной компромисс» в этом режиме; см. обзор Дитером ван Мелкебеком нижних границ пространственно-временного пространства SAT за 2008 год.
Если вы ограничиваете себя многолучевыми машинами Тьюринга, вы можете доказать бесконечно часто. Это было доказано Рахулом Сантанамом и следует из аналогичной нижней границы, известной для PALINDROMES в этой модели. Мы полагаем, что вы сможете доказать квадратичную нижнюю границу, которая «не зависит от модели», но которая была неуловимой в течение некоторого времени.
Для неоднородных цепей с ограниченным разветвлением, я не знаю никакой нижней границы глубины лучше, чем .
источник
источник
Мое понимание такое же, как у Льва Рейзина. Возможно, что существует детерминированный полный алгоритм для SAT, который работает в пространстве O (n) и во времени O (n). Удивительно, что существование такого эффективного алгоритма не запрещено.
источник