¿Por qué a menudo se requiere construcibilidad espacial en el teorema de Savitch?

Question

Cuando se afirma el famoso teorema de Savitch, uno a menudo ve el requisito de que $ s (n) $ sea espacio constrible (curiosamente, se omite en Wikipedia). Mi simple pregunta es: ¿por qué necesitamos esto? Entiendo que el requisito de $ S (n) $ está en $ omega ( log n) $, que es claro a partir de la prueba. Pero ninguna prueba que haya visto hasta ahora usa explícitamente que $ s (n) $ es construcible en el espacio.

Mi explicación: para llamar al alcance del procedimiento (o ruta o como quiera llamarlo), el último parámetro debe ser "deletreado", y para no dejar nuestros límites espaciales de S (n) para una llamada , no debemos necesitar más de $ s (n) $ espacio para escribirlo.

Answer 1

Creo que su explicación es correcta. La subrutina ST-REACHE obtiene $ (S, T, ell) $ como entrada, y encuentra si $ T $ es accesible de $ S $ por $ ell $ pasos. $ S $ y $ T $ serán las configuraciones iniciales y finales, y $ ell = 2^{o (s (n))} $, el límite superior en el número de configuraciones diferentes.

Para establecer $ ell $ uno, debe poder calcular $ s (n) $ (o más bien, $ 2^{o (s (n))} $). Si este proceso toma más de $ o (s^2 (n)) $ espacio, entonces toda la máquina tendrá espacio más que el permitido. Es posible que incluso $ o (s^2 (n)) $ sea demasiado debido a la llamada recursiva a St-Right (¿hay alguna otra razón posible?), Pero no lo verifiqué.

Answer 2

Esto se elabora muy bien en el libro de texto de la teoría del cálculo de Dexter Kozen, en el Capítulo 2.

El teorema de Savitch (Teorema 1 en su artículo) dice: Si $ s (n) ge log n $, entonces $ text {nspace} (s (n)) subseteq text {dspace} (s (n)^ 2) $. La construcción del espacio a menudo parece suponerse en una prueba, pero este requisito se puede eliminar reiniciando la búsqueda con un límite de espacio fijo que puede aumentar con cada intento.

Quizás surge la confusión porque el papel savitch original se trata en gran medida de investigar si $ text {nspace} (s (n)) no subseteq text {dspace} (s (n)) $. Por lo tanto, gasta mucho esfuerzo en funciones construibles con espacio, debido a la siguiente observación del documento:

Es natural preguntar si hay alguna función de almacenamiento cuyas clases de complejidad determinista y no determinista son iguales. La respuesta fue dada por Manuel Blum y es "sí". Blum demostró que hay funciones de almacenamiento arbitrariamente grandes L (n) de modo que un conjunto se acepta dentro del almacenamiento determinista L (n) si, y solo si, se acepta dentro del almacenamiento no determinista L (n). Sin embargo, estas funciones L (n) no están "bienes bienes" y el Teorema 3 no se aplica a ellas.

(Aquí "bien comportado" se refiere a las funciones construibles con espacio, llamadas mensurable por Savitch.)