Problemas de cálculo infinitamente grandes pero localmente finitos

Esta pregunta está inspirada en un comentario que Jukka Suomela hizo sobre otra pregunta .

¿Cuáles son ejemplos de problemas de cálculo (y algoritmos) infinitamente grandes pero localmente finitos?

En otras palabras, ¿cuáles son ejemplos de cálculos que se detienen en un tiempo finito, en el que cada máquina de Turing lee y procesa solo datos finitos, pero en conjunto el cálculo resuelve un problema de tamaño infinito si hay infinitas máquinas conectadas en red?

Solo para dar algunas ideas de lo que es posible (pero algo no trivial), aquí hay un ejemplo: un algoritmo distribuido que encuentra un empaque de borde máximo en un gráfico de grado acotado.

Definición del problema

Dado un gráfico simple no dirigido , un empaque de borde (o coincidencia fraccional) asocia un peso w ( e ) con cada borde e ∈ E de tal manera que para cada nodo v ∈ V , el peso total de los bordes incidentes en v es como máximo 1 . Un nodo está saturado si el peso total de los bordes incidentes es igual a 1 . Un empaque de borde es máximo si todos los bordes tienen al menos un punto final saturado (es decir, ninguno de los pesos se puede extender con avidez).$G = (V,E)$$w(e)$$e \in E$$v \in V$$v$$1$$1$

Observe que una coincidencia máxima define un empaquetamiento de borde máximo (conjunto w ( e ) = 1 iff e ∈ M ); por lo tanto, es fácil de resolver en un entorno centralizado clásico (suponiendo que G es finito).$M \subseteq E$$w(e) = 1$$e \in M$$G$

Los empaques de borde en realidad tienen algunas aplicaciones, al menos si uno define una aplicación en el sentido TCS habitual: el conjunto de nodos saturados forma una aproximación de de una cubierta de vértice mínima (por supuesto, esto solo tiene sentido en el caso de un G finito ) .$2$$G$

Modelo de computación

Asumiremos que hay una constante global tal que el grado de cualquier v ∈ V es como máximo Δ .$\Delta$$v \in V$$\Delta$

Para mantener esto tan cerca del espíritu de la pregunta original, definamos el modelo de cálculo de la siguiente manera. Suponemos que cada nodo es una máquina de Turing, y un borde { u , v } ∈ E es un canal de comunicación entre u y v . La cinta de entrada de v codifica el grado en grados ( v ) de v . Para cada v ∈ V , los bordes incidentes con v están etiquetados (en un orden arbitrario) con los enteros 1 , 2 , $v \in V$$\{u,v\} \in E$$u$$v$$v$$\deg(v)$$v$$v \in V$$v$ ; estos se denominanetiquetas de borde locales(la etiqueta de { u , v } ∈ E puede ser diferente para u y v ). La máquina tiene instrucciones con las que puede enviar y recibir mensajes a través de cada uno de estos bordes; una máquina puede dirigirse a sus vecinos utilizando las etiquetas de borde locales.$1,2,\dotsc,\deg(v)$$\{u,v\} \in E$$u$$v$

Es necesario que las máquinas de calcular una ventaja válida embalaje de G . Más precisamente, cada v ∈ V tiene que imprimir en su cinta de salida una codificación de w ( e ) para cada borde e incidente a v , ordenada por las etiquetas de borde locales, y luego detenerse.$w$$G$$v \in V$$w(e)$$e$$v$

Decimos que un algoritmo distribuido encuentra un empaque de borde máximo en el tiempo T , si lo siguiente se cumple para cualquier gráfico G de grado máximo Δ , y para cualquier etiquetado de borde local de G : si reemplazamos cada nodo de G con una copia idéntica de la máquina Turing A e inicie las máquinas, luego, después de los pasos T, todas las máquinas han impreso una solución válida (globalmente consistente) y se han detenido.$A$$T$$G$$\Delta$$G$$G$$A$$T$

Infinitos

Ahora todo lo anterior tiene mucho sentido incluso si el conjunto de nodos es infinitamente contable.$V$

La formulación del problema y el modelo de cálculo no tienen ninguna referencia a , directa o indirectamente. La longitud de la entrada para cada máquina de Turing está limitada por una constante.$|V|$

Lo que se sabe

El problema se puede resolver en tiempo finito incluso si es infinito.$G$

El problema no es trivial en el sentido de que es necesaria alguna comunicación. Además, el tiempo de ejecución depende de . Sin embargo, para cualquier Δ fijo , el problema puede resolverse en tiempo constante independientemente del tamaño de G ; en particular, el problema se puede resolver en gráficos infinitamente grandes.$\Delta$$\Delta$$G$

No he verificado cuál es el tiempo de ejecución más conocido en el modelo definido anteriormente (que no es el modelo habitual utilizado en el campo). Sin embargo, un tiempo de ejecución que es polinomial en debería ser bastante fácil de lograr, y creo que un tiempo de ejecución que es sublineal en Δ es imposible.$\Delta$$\Delta$

Encontrar la próxima generación de un autómata celular .

Esto se puede resolver como lo describió en tiempo constante. $\;$ (es decir, independiente de la entrada)

Esencialmente, cada problema que es al menos tan difícil como la coloración requiere un algoritmo con un tiempo de ejecución que dependa del número de nodos en la red y, por lo tanto, no puede funcionar en un gráfico infinito pero localmente finito. Esto se desprende del registro seminal de Linial * n límite inferior.

Esto no se ajusta a su definición, pero creo que solo por la falta de uniformidad. Antes de mostrar la paridad no estaba en$AC^0$, Sipser (creo que lo fue) demostró que cualquier función de paridad infinita (una función en muchas variables que cambia la salida cada vez que se cambia una sola entrada) no podría resolverse en "infinitivo $AC^0$".