¿El mejor espacio actual para el SAT?

¿Cuáles son los mejores límites inferiores del espacio actual para SAT?

Con un límite inferior de espacio, me refiero al número de celdas de cintas de trabajo utilizadas por una máquina de Turing que utiliza un alfabeto binario de cintas de trabajo. Un término aditivo constante es inevitable ya que una TM puede usar estados internos para simular cualquier número fijo de celdas de cinta de trabajo. Sin embargo, estoy interesado en controlar la constante multiplicativa que a menudo se deja implícita: la configuración habitual permite la compresión constante arbitraria a través de alfabetos más grandes, por lo que la constante multiplicativa no es relevante allí, pero con un alfabeto fijo debería ser posible tenerla en cuenta.

Por ejemplo, SAT requiere más de espacio; de lo contrario, este límite superior del espacio conduciría a un límite superior de tiempo de por simulación, y por lo tanto el límite inferior de espacio-tiempo combinado para SAT sería ser violado (ver la pregunta vinculada). También parece posible mejorar este argumento para argumentar que SAT requiere al menos espacio para algún pequeño positivo que es algo así como , donde es el exponente constante en la simulación de un espacio limitado TM por un TM con límite de tiempo. $\log\log n + c$ $n^{1+o(1)}$ $n^{1.801+o(1)}$ $\delta\log n + c$ $\delta$ $0.801/C$ $C$

Desafortunadamente, $C$ suele ser bastante grande (y ciertamente al menos 2 en la simulación habitual, donde las cintas de un TM se codifican primero en una sola cinta a través de un alfabeto más grande). Tales límites con $\delta \ll 1$ son bastante débiles, y estaría especialmente interesado en un límite inferior de espacio de $\log n + c$ . Un límite inferior de tiempo incondicional de pasos de $\Omega(n^d)$ , para una constante bastante grande $d > 1$ , implicaría un límite inferior de este espacio mediante simulación. Sin embargo, los límites inferiores de tiempo de $\Omega(n^d)$ para $d>1$ no se conocen actualmente, y mucho menos para grande $d$ .

Dicho de otra manera, estoy buscando algo que sería una consecuencia de los límites inferiores de tiempo superlineales para SAT, pero que podría ser posible obtener de forma más directa.

cc.complexity-theory sat lower-bounds space-bounded space-complexity András Salamon
fuente

como en esa otra respuesta (p. ej., por RW), centrarse en los límites inferiores del tiempo o el espacio por separado parece estar fuera del alcance y tener solo límites débiles / genéricos conocidos, y la investigación líder en el área parece dar lugar a un concepto relativamente más nuevo de complejidad combinada tiempo-espacio.

vzn

Respuestas:

Parece que el mejor límite conocido (para máquinas Turing de múltiples capas) es logarítmico.

Supongamos que bits de worktape binario es suficiente para decidir si cualquier bits fórmula CNF es satisfiable, por todo lo suficientemente grande como . Según la simulación estándar, una TM con estados que utiliza como máximo bits de espacio puede simularse mediante una TM que tenga como máximo diferentes configuraciones . Cada vez que la máquina acepta, hay una secuencia de movimientos (no deterministas) que alcanzan un estado de aceptación que es tan largo como este número de configuraciones. Cuando , esto es como máximo (tenga en cuenta que permanece igual para todas las longitudes de entrada $\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$ ) En una cinta de contador separada, puede escribir primero esta cantidad en unario, luego en cada paso de la simulación borre uno de los símbolos del contador y termine el cálculo si alguna vez se queda sin símbolos de contador. Esto crea un factor constante de sobrecarga (algo así como 3), que es absorbido por el término en el exponente. Por lo tanto, pasos son suficientes. $M$ $o(1)$ $2^{s(2+o(1))}$

Asumiendo , entonces el producto espacio-tiempo es como máximo . $s \le \delta\log n$ $\delta\log n2^{\delta\log n(2+o(1))} = n^{\delta(2+o(1))}$

Rahul Santhanam demostró en 2001 (ver doi: 10.1016 / S0020-0190 (00) 00227-1 ) que el producto espacio-tiempo para una máquina Turing que decide SAT debe ser al menos ; Su argumento se aplica también a las máquinas no deterministas. Por lo tanto, , y al menos bits de cinta de trabajo binaria son necesarios. $\Omega(n^{2-o(1)})$ $\delta \ge 1$ $\log n$

Más generalmente, las cintas de trabajo adicionales y un alfabeto de cinta de trabajo más grande cambian el exponente por un factor constante. Esto finalmente reduce el factor , pero el límite inferior del espacio sigue siendo . $\delta$ $\Omega(\log n)$

András Salamon
fuente

Tal vez podamos probar un espacio límite inferior para SAT de esta manera (pero no estoy seguro con el análisis de límite / asintótico, por lo que mi respuesta puede ser totalmente incorrecta). $\log n$

En un modelo de máquina de Turing con una cinta de entrada de solo lectura y una cinta de trabajo, ambas sobre alfabeto binario , por cada decisor con estados en una entrada de tamaño tenemos que: $\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)$

de lo contrario, la máquina de Turing se repetirá para siempre (el componente representa todas las configuraciones de cinta posibles, el componente representa las posiciones del cabezal de la cinta de entrada, mientras que el componente representa las posiciones del cabezal de la cinta de trabajo). En una cinta de una sola cabeza TM sobre el alfabeto binario (1) se convierte en . $2^{S(n)}$ $n$ $S(n)$ $T(n) \leq c 2^{S(n)} S(n)$

Multiplicando ambos términos por y aplicando el intercambio espacio-tiempo general para SAT, obtenemos: $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$

Por lo tanto, elegir un límite superior de espacio como para SAT conduciría a una contradicción, de hecho $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$

Marzio De Biasi
fuente

Parece que hay al menos dos formas generales de mostrar que un límite superior conduce a una contradicción. Principalmente tenía en mente usar la desigualdad (esencialmente idéntica, pero un poco más fácil de trabajar) para alguna constante . El último paso que usted proporciona también puede hacerse más fuerte, como una contradicción sigue incluso de para .

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ás Salamon

@ AndrásSalamon: en el lado de , no puede esperar mejoras fáciles: de S. Buss y R. Williams. Límites en las pruebas de comercio de alternancia para los límites inferiores del espacio-tiempo, 2012: "Mostramos que las nuevas técnicas son demostrablemente necesarias para probar cualquier límite inferior de espacio-tiempo mejor para el problema de la satisfacción. Es decir, el método de" comercio de alternancia pruebas "utilizadas para establecer que SAT no se puede resolver en tiempo y espacio no puede probar un límite inferior de tiempo, por cada ". Tienes alguna idea :-)?

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$

Marzio De Biasi

Creo que esto es lo más lejos que se puede llegar utilizando los límites espacio-temporales, precisamente porque el enfoque de Ryan es tan amplio como estos límites.

András Salamon

Incluso para almacenar una instancia SAT necesita y leerla necesita tiempo . ¿No prueba esto ST límite inferior?

Ω (n)

$\Omega(n)$

Ω (n)

$\Omega(n)$

Ω (n^{2})

$\Omega(n^2)$

T ....

@Turbo, no está claro que cada algoritmo para decidir SAT tenga que almacenar la instancia: probar un límite inferior de espacio determinista bit mostrará .

Ω (n)

$\Omega(n)$

L ⊊ N P

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

András Salamon