Resumen Técnico: La alcancabilidad de 3-VASS está en EXPSPACE

Planteamiento del Problema

El artículo aborda el problema de la alcancabilidad para los Sistemas de Adición de Vectores con Estados de 3 dimensiones (3-VASS). Un VASS es un autómata de estados finitos equipado con un número fijo de contadores (dimensiones) que contienen enteros no negativos. El problema de la alcancabilidad pregunta si una configuración objetivo (estado y valores de los contadores) es alcanzable desde una configuración de origen mediante una secuencia de transiciones válidas.

Aunque el problema de la alcancabilidad general de VASS (donde la dimensión es parte de la entrada) fue demostrado como ACKERMANN-completo en 2021, la complejidad exacta para dimensiones fijas $d > 2$ sigue siendo una cuestión abierta central. Específicamente para 3-VASS:

• Cota Inferior: Se sabe que el problema es PSPACE-duro, heredado del caso de 2 dimensiones.
• Cota Superior Previa: Hasta este trabajo, la mejor cota superior conocida era 2-EXPSPACE (espacio doble exponencial), establecida por Czerwiński et al. (ICALP 2025). Antes de eso, los algoritmos eran no elementales.

El artículo tiene como objetivo cerrar la brecha entre la cota inferior PSPACE y la cota superior 2-EXPSPACE, demostrando que la alcancabilidad de 3-VASS pertenece a EXPSPACE (espacio exponencial simple).

Metodología y Estrategia de Demostración

El núcleo de la demostración es establecer un límite de longitud doblemente exponencial para las ejecuciones más cortas entre dos configuraciones en un 3-VASS. Si la longitud de la ejecución más corta está acotada por $N^{2^{poly(k)}}$ (don donde $N$ es el tamaño de la entrada y $k$ es el número de componentes fuertemente conexos), entonces la alcancabilidad puede decidirse en EXPSPACE adivinando de forma no determinista un camino de esa longitud.

Los autores emplean una estrategia de reducción jerárquica y una técnica de demostración de separación de preocupaciones, refinando la clase de instancias de 3-VASS en una secuencia de subclases. Este enfoque evita la inducción "anidada" que llevó a cotas triple exponenciales en trabajos anteriores.

1. Clasificación Jerárquica de VASS

El artículo define una jerarquía de subclases para 3-VASS, ordenadas por creciente generalidad:
$$\text{DiagVASS}_3 \subsetneq \text{Semi-diagVASS}_3 \subsetneq \text{PumpVASS}_3 \subsetneq \text{Semi-pumpVASS}_3 \subsetneq \text{SeqVASS}_3$$

• DiagVASS: Instancias donde existen ciclos "diagonales" tanto hacia adelante como hacia atrás (ciclos que pueden bombear todos los contadores positivamente).
• PumpVASS: Instancias donde existen ciclos "bombables" (pumpable) tanto hacia adelante como hacia atrás (ciclos que pueden bombear al menos un contador positivamente).
• SeqVASS: VASS secuencial general, donde la ejecución atraviesa una secuencia de Componentes Fuertemente Conexos (SCC) conectados por puentes.

La demostración procede estableciendo el límite de longitud para la clase más restrictiva (DiagVASS) y luego utilizando autorreducciones controladas por longitud para transferir estos límites a las clases más generales.

2. Componentes Técnicos Clave

A. Representación Eficiente de Conjuntos de Alcancabilidad (VASS Geométricamente 2D)

Una herramienta crucial es el análisis de VASS geométricamente 2-dimensional, donde todas las ejecuciones permanecen entre dos planos 2D paralelos. Los autores extienden los resultados de Czerwiński et al. para mostrar que el conjunto de alcancabilidad de tales sistemas, incluso cuando se parte de un "conjunto híbrido" (un vector base más un conjunto periódico restringido), puede representarse como una unión finita de conjuntos híbridos con descripciones de tamaño polinómico. Esto permite la manipulación eficiente de los conjuntos de alcancabilidad sin incurrir en un crecimiento exponencial en el tamaño de la representación.

B. Manejo de Instancias Diagonales No Anchas (Non-Wide)

Para DiagVASS, los autores distinguen entre instancias "anchas" (wide) y "no anchas" (non-wide).

• Anchas: El cono secuencial del sistema contiene todos los vectores positivos. Estas se manejan reduciéndolas a resultados conocidos.
• No Anchas: Los autores demuestran que en instancias diagonales no anchas, los conos secuenciales del prefijo y el sufijo de la ejecución están separados por un hiperplano. Esta separación geométrica implica que los valores de los contadores en los componentes intermedios están restringidos dentro de un par de planos 2D paralelos. En consecuencia, el problema puede transformarse en una secuencia de instancias de VASS geométricamente 2-dimensionales, permitiendo la aplicación de las técnicas de representación eficiente mencionadas anteriormente para derivar un límite doblemente exponencial.

C. Autorreducción Controlada por Longitud

Para pasar de PumpVASS y SeqVASS a DiagVASS, el artículo introduce una autorreducción controlada por longitud.

• Extracción de Diagonalidad Conjunta: Para una instancia bombable, los autores muestran que se puede extraer un prefijo "conjuntamente diagonal" (una secuencia de ciclos que colectivamente bombean todos los contadores).
• Reducción: Este prefijo se utiliza para construir una nueva instancia de VASS con menos componentes (o una estructura más simple) que es diagonal. El tamaño de esta nueva instancia está controlado por la función de longitud de la clase objetivo.
• Evitar el Anidamiento: A diferencia de enfoques previos que anidaban la función de límite de longitud (por ejemplo, $h_k(h_{k-1}(\dots))$), este método asegura que el límite de longitud aparezca solo una vez en el lado derecho de la recurrencia. Este cambio estructural es lo que reduce la complejidad de 2-EXPSPACE a EXPSPACE.

Contribuciones y Resultados Clave

1. Teorema Principal: El problema de la alcancabilidad de 3-VASS está en EXPSPACE.

   • Esto es válido tanto para codificaciones unarias como binarias de la entrada.
   • La demostración se basa en mostrar que para cualquier 3-VASS de $k$ componentes, la longitud de la ejecución más corta está acotada por $size(V, s, t)^{2^{poly(k)}}$.

2. Paisaje de Complejidad Refinado: El artículo proporciona un análisis detallado de la complejidad de las subclases de 3-VASS:

   • DiagVASS3: Demostrado que está en EXPSPACE (mejorando la cota previa de 2-EXPSPACE).
   • PumpVASS3: Demostrado que admite ejecuciones doblemente exponenciales de longitud corta.
   • SeqVASS3: Demostrado que admite ejecuciones de longitud doblemente exponencial mediante autorreducción a PumpVASS.

3. Avance Metodológico: El artículo introduce un análisis de bombabilidad jerárquica y una estrategia de separación de preocupaciones. Al descomponer el problema en subproblemas geométricamente 2D y utilizar autorreducciones que respetan la jerarquía de componentes, los autores eliminan el crecimiento triple exponencial inherente a las demostraciones inductivas previas.

Significancia y Reivindicaciones

El artículo afirma avanzar significativamente en la comprensión del problema de la alcancabilidad de 3-VASS, un desafío de larga data en la informática teórica.

• Estrechamiento de la Cota: El resultado estrecha la brecha de complejidad para 3-VASS de una cota superior doblemente exponencial a una exponencial simple. Aunque la cota inferior sigue siendo PSPACE, los autores señalan que la reducción de un VASS general a un VASS bombable probablemente no puede hacerse en espacio polinómico, lo que sugiere que 3-VASS podría ser efectivamente EXPSPACE-duro.
• Fundamento para Trabajos Futuros: El artículo establece explícitamente que determinar la complejidad exacta (PSPACE vs. EXPSPACE) sigue siendo una cuestión abierta. Destaca que una prueba definitiva de EXPSPACE-dureza requeriría un ejemplo de un 3-VASS que admita ejecuciones más cortas doblemente exponenciales, lo cual es actualmente desconocido.
• Implicaciones para Dimensiones Superiores: Los autores sugieren que su perspectiva sobre el acotamiento de ejecuciones cortas podría ser fructífera para analizar VASS en dimensiones $d \ge 4$, donde las cotas superiores actuales están lejos de ser elementales.

En resumen, el artículo proporciona una prueba rigurosa de que la alcancabilidad de 3-VASS es resoluble en espacio exponencial, utilizando una combinación novedosa de argumentos de separación geométrica, representaciones eficientes de conjuntos de alcancabilidad y un marco de autorreducción refinado que evita el crecimiento de complejidad de los métodos anteriores.