Daily Arxiv

Esta página recopila y organiza artículos sobre inteligencia artificial publicados en todo el mundo.
La información aquí presentada se resume utilizando Google Gemini y el sitio se gestiona sin fines de lucro.
Los derechos de autor de los artículos pertenecen a sus autores y a las instituciones correspondientes; al compartir el contenido, basta con citar la fuente.

$TIME[t] \subseteq SPACE[O(\sqrt{t})]$ mediante compresión de altura del árbol

Created by
  • Haebom

Autor

Logan Nye

Describir

Este artículo prueba una simulación de espacio de raíz cuadrada para una máquina de Turing multicinta determinista, mostrando que $\TIME[t] \subseteq \SPACE[O(\sqrt{t})]$. La clave es el Teorema de Compresión de Altura, que reconstruye el árbol de cálculo compacto estándar de profundidad izquierda para la ejecución respetando bloques en un árbol binario uniforme (y logarítmico), manteniendo $O(b)$ operaciones en nodos hoja, $O(1)$ operaciones en nodos internos y aristas verificables en logaritmo, a la vez que mantiene $O(\log T)$ profundidad de pila de evaluación para $T = \lceil t/b \rceil$ a lo largo de cualquier ruta DFS. La corrección semántica entre fusiones se prueba mediante la reproducción exacta de $O(b)$ ventanas en una interfaz única. Utilizamos recursión de punto medio (balanceada), potencial por ruta para restringir las interfaces activas simultáneamente a $O(\log T)$ y restricciones de grado para reemplazar fusiones múltiples con combinadores binarios balanceados. Algorítmicamente, el DFS sin punteros y la transmisión sin índices, junto con un motor de reproducción algebraica que utiliza asignaciones de orden constante a campos de tamaño constante, garantizan tokens de tamaño constante por nivel y eliminan los contadores anchos. Esto proporciona un compromiso aditivo de $S(b)=O(b + \log(t/b))$ para el tamaño de bloque $b \ge b_0$, donde $b_0 = \Theta(\log t)$, lo que da un espacio de $O(\sqrt{t})$ bajo la opción estándar de $b = \Theta(\sqrt{t})$. El umbral $b_0$ excluye los bloques degenerados donde el direccionamiento de scratch domina el espacio de ventana. Esta estructura es uniforme, relativista y robusta a las opciones del modelo estándar. Los resultados incluyen una cota superior del programa de ramificación $2^{O(\sqrt{s})}$ para circuitos de entrada con restricciones de tamaño $s$, una cota inferior mejorada en tiempo cuadrático para el problema $\SPACE[n]$-completo mediante argumentos jerárquicos estándar, y un solucionador con certificación espacial $O(\sqrt{t})$. Bajo supuestos explícitos de localidad, este marco se extiende a modelos geométricos $d$-dimensionales.

Takeaways, Limitations

Takeaways:
Presentamos una nueva simulación del espacio de raíz cuadrada para una máquina de Turing multicinta determinista ($\TIME[t] \subseteq \SPACE[O(\sqrt{t})]$).
Prueba de un límite superior en $2^{O(\sqrt{s})}$ programas de rama para circuitos de abanico de entrada con restricciones de tamaño $s$.
Prueba de un límite inferior de segundo orden mejorado para el problema $\SPACE[n]$-completo.
Sugerimos la posibilidad de desarrollar un solucionador de autenticación de $O(\sqrt{t})$-espacio.
Extensibilidad a modelos geométricos de dimensión $d$ (bajo supuestos de localidad explícitos).
Limitations:
Complejidad de la prueba.
La extensión a modelos geométricos sólo es posible bajo supuestos de localidad explícitos.
Dificultad en la implementación real.
👍