Лучшая текущая космическая нижняя граница для SAT?

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

С нижней границей пробела здесь я имею в виду количество ячеек рабочей ленты, используемых машиной Тьюринга, которая использует двоичный алфавит рабочей ленты. Постоянный аддитивный член неизбежен, поскольку TM может использовать внутренние состояния для моделирования любого фиксированного числа ячеек рабочей ленты. Тем не менее, я заинтересован в управлении мультипликативной константой, которая часто остается неявной: обычная настройка допускает произвольное сжатие констант с помощью больших алфавитов, поэтому мультипликативная константа там не актуальна, но с фиксированным алфавитом должна быть возможность принять это во внимание.

Например, SAT требует больше чем пробела; в противном случае эта верхняя граница пространства привела бы к временной верхней границе путем моделирования, и, таким образом, объединенная нижняя граница пространства-времени для SAT быть нарушенным (см. связанный вопрос). Также представляется возможным улучшить этот аргумент, утверждая, что для SAT требуется как минимум пространство для некоторого небольшого положительного значения , например , где - постоянный показатель в моделировании ограниченного пространством ТМ ограниченной по времени ТМ. $\log\log n + c$ $n^{1+o(1)}$ $n^{1.801+o(1)}$ $\delta\log n + c$ $\delta$ $0.801/C$ $C$

К сожалению, обычно довольно большой (и, конечно, по крайней мере 2 в обычном моделировании, где ленты TM сначала кодируются на одной ленте с помощью большего алфавита). Такие оценки с довольно слабые, и меня особенно заинтересовала бы нижняя граница пространства . Безусловная нижняя граница шагов для некоторой достаточно большой константы подразумевает такую нижнюю границу пространства посредством моделирования. Однако нижние границы времени для в настоящее время не известны, не говоря уже о больших . $C$ $\delta \ll 1$ $\log n + c$ $\Omega(n^d)$ $d > 1$ $\Omega(n^d)$ $d>1$ $d$

Иными словами, я ищу что-то, что могло бы быть следствием нижних границ суперлинейного времени для SAT, но которое можно было бы получить более непосредственно.

cc.complexity-theory sat lower-bounds space-bounded space-complexity Андраш Саламон
источник

как и в этом другом ответе (например, RW), сосредоточение внимания на нижних границах времени или пространства в отдельности, кажется, недостижимо и имеет лишь слабые / общие известные границы, и ведущие исследования в этой области, как представляется, дают начало относительно новой концепции комбинированной пространственно-временной сложности.

августа

Ответы:

Похоже, лучшая известная оценка (для многолентовых машин Тьюринга) является логарифмической.

Предположим, что битов двоичной рабочей ленты достаточно, чтобы решить, является ли любая битная формула CNF удовлетворительной для всех достаточно больших . С помощью стандартного моделирования TM с состояниями, использующими не более битов пространства, может моделироваться TM, который имеет не более различных конфигураций , Всякий раз, когда машина принимает, есть последовательность (недетерминированных) ходов, достигающих принимающего состояния, которое не превышает этого количества конфигураций. Когда , это не более (обратите внимание, что остается одинаковым для всех входных длин $\delta\log n$ $n$ $n$ $q$ $s$ $qns2^s = 2^{s+\log n + \log s + \log q}$ $s = \Omega(\log n)$ $2^{s(2+o(1))}$ $q$ $n$ ). На отдельной счетной ленте может сначала записать эту величину в унарном виде, затем на каждом этапе моделирования стирать один из символов счетчика и завершать вычисление, если в нем когда-либо заканчиваются символы счетчика. Это создает постоянный коэффициент накладных расходов (что-то вроде 3), который поглощается членом в показателе степени. Следовательно, шагов достаточно. $M$ $o(1)$ $2^{s(2+o(1))}$

По предположению , так что пространственно-временное произведение не больше . $s \le \delta\log n$ $\delta\log n2^{\delta\log n(2+o(1))} = n^{\delta(2+o(1))}$

В 2001 году Рахул Сантанам показал (см. Doi: 10.1016 / S0020-0190 (00) 00227-1 ), что пространственно-временное произведение для машины Тьюринга, решающей SAT, должно быть не менее ; его аргумент применим и к недетерминированным машинам. Следовательно , требуется и, по крайней мере, бит двоичной рабочей ленты. $\Omega(n^{2-o(1)})$ $\delta \ge 1$ $\log n$

В целом, дополнительные рабочие ленты и больший алфавит рабочих таблиц изменяют показатель степени на постоянный коэффициент. Это в конечном итоге уменьшает фактор , но нижняя граница пространства по-прежнему . $\delta$ $\Omega(\log n)$

Андраш Саламон
источник

Возможно, мы сможем доказать нижнюю границу пространства для SAT таким образом (но я не уверен в предельном / асимптотическом анализе, поэтому мой ответ может быть полностью неверным). $\log n$

На модели машины Тьюринга с одной входной лентой только для чтения и одной рабочей лентой, оба над двоичным алфавитом , для каждого решающего элемента с состояниями на входе размера мы имеем следующее: $\Sigma = \{0,1\}$ $c$ $n$

T (n) \leq c 2^{S (n)} n S (n) (1)

$T(n) \leq c \, 2^{S(n)} \, n \, S(n) \quad (1)$

в противном случае машина Тьюринга будет зацикливаться вечно ( компонент представляет все возможные конфигурации ленты, компонент представляет позиции входной головки ленты, а компонент представляет позиции рабочей головки ленты). На одной ленте одиночная головка TM над двоичным алфавитом (1) становится . $2^{S(n)}$ $n$ $S(n)$ $T(n) \leq c 2^{S(n)} S(n)$

Умножив оба члена на и применив общий пространственно-временной компромисс для SAT, мы получим: $S(n)$

n^{1.801 + o (1)} \leq S (n) \cdot T (n) \leq c S (n)^{2} 2^{S (n)} n

$n^{1.801+o(1)} \leq S(n)\cdot T(n) \leq c \, S(n)^2 \, 2^{S(n)} \, n$

Поэтому выбор верхней границы пространства, такой как для SAT, может привести к противоречию, действительно $S(n) \leq (\log n)^{1 - \epsilon}$

lim_{n \to \infty} \frac{n^{1.801}}{c ((\log n)^{1 - ϵ})^{2} 2^{(\log n)^{1 - ϵ}} n} =

$\lim_{n \to \infty} \frac{n^{1.801}}{ c \, ((\log n)^{1-\epsilon})^2 2^{(\log n)^{1-\epsilon}} n } =$

lim_{n \to \infty} (0.801 \cdot \log n - \log c - 2 (1 - ϵ) \log (\log n) - (\log n)^{1 - ϵ}) = \infty

$\lim_{n \to \infty} \Big( 0.801 \cdot \log n - \log c - 2 (1- \epsilon) \log (\log n) - (\log n)^{1-\epsilon}\Big) = \infty$

Марцио де Биаси
источник

Кажется, что есть по крайней мере два общих способа показать, что верхняя граница приводит к противоречию. В первую очередь я имел в виду , используя ( по существу идентичны, но немного легче работать с) неравенство для некоторой константы . Последний шаг вы предоставите также может быть сильнее, как противоречие вытекает даже из для .

o (\log n)

$o(\log n)$

T (n) \leq 2^{\log n + C . S (n)}

$T(n) \le 2^{\log n + C.S(n)}$

C

$C$

S (n) \leq δ \log n

$S(n) \le \delta\log n$

δ < 0.801 / C

$\delta < 0.801/C$

Андрас Саламон

@ AndrásSalamon: со стороны нельзя ожидать легких улучшений: от С. Бусса и Р. Уильямса. Ограничения на доказательства чередования торговли для нижних границ пространства-времени, 2012: «Мы показываем, что новые методы доказуемо необходимы для того, чтобы доказать лучшие нижние оценки пространства-времени для проблемы выполнимости. То есть метод« чередования торговли » доказательства "используются для установления того, что SAT не может быть решена за времени, а пространство не может доказать time нижняя граница для каждого ". Есть ли у вас какие-либо идеи :-)?

S \cdot T

$S\cdot T$

n^{2 \cos (π / 7)}

$n^{2\cos(\pi /7)}$

n^{o (1)}

$n^{o(1)}$

n^{2 \cos (π / 7)} + ϵ

$n^{2\cos(\pi /7)}+\epsilon$

ϵ > 0

$\epsilon >0$

Марцио Де Биаси

Я думаю, что речь идет о том, насколько далеко можно пойти, используя границы пространства-времени, именно потому, что подход Райана настолько далеко, насколько эти границы идут.

Андрас Саламон

Чтобы даже сохранить экземпляр SAT, вам нужен и прочитать его, вам нужно время. Разве это не доказывает нижнюю границу ST?

Ω (n)

$\Omega(n)$

Ω (n)

$\Omega(n)$

Ω (n^{2})

$\Omega(n^2)$

T ....

@ Турбо, не ясно, что каждый алгоритм, чтобы решить, что SAT должен хранить экземпляр: доказательство нижней границы детерминированного пространства покажет .

Ω (n)

$\Omega(n)$

L ⊊ N P

$\mathsf{L} \subsetneq \mathsf{NP}$

Саламон,