Redes de automatas y complejidad computacional

Abstract

El presente trabajo consiste en el estudio de la complejidad computacional en algunas redes de autómatas. En particular en el problema de decisión, que llamamos PER, el cual consiste en predecir cambios de estado en un nodo determinado cuando la red se actualiza según una regla determinada. Dentro de los primeros en introducir complejidad computacional a los autómatas celulares (CA) y sistemas relacionados podemos destacar a C. Moore [19] quien estudió la regla de la mayoría estricta en lattices d-dimensionales, y a T. Neary con D.Woods [23], que prueban la P-Complitud de la regla 110 en autómatas unidimensionales. Estos estudios son interesantes porque, por un lado, usualmente es muy difícil obtener caracterizaciones del comportamiento general de la dinámica de un autómata celular en el tiempo; y por otro lado, están relacionados con el procesamiento paralelo de la información y algoritmos, ya que algunos CA son capaces de emular una máquina de Turing universal. Luego, la idea es construir un puente entre estos dos aspectos del problema: la naturaleza de su dinámica y sus capacidades algorítmicas. Por lo general estos trabajos se enfocan en acotar el problema por arriba , determinando P-Complitud. Este trabajo es novedoso en el sentido que a lo anterior agregamos un acota- miento por abajo , buscando demostrar que cuando el problema no es P-Completo, entonces debe ser eficientemente paralelizable, es decir, pertenecer a la clase NC. Esto lo haremos va- riando primero la topología de la red considerando siempre un modo de iterar paralelo, y posteriormente determinando la influencia de distintos modos de iterar en la complejidad. En términos más concretos, estudiaremos la complejidad computacional de Bootstrap Percolation (Capítulo 2). El resultado principal es que, para esta regla, el problema de decisión PER está en NC si restringimos al grafo que define a la red a pertenecer a la familia que tiene grado máximo pequeño, y en caso contrario el problema es P-Completo. Luego, en el Capítulo 3, cambiaremos a la regla de la mayoría estricta, donde el principal resultado del capítulo será que para esta regla PER es P-Completo en la familia de grafos planares. Finalmente, en el cuarto capítulo estudiaremos cómo varían los resultados anteriores cuando consideramos distintos modos de actualizar los estados de la red. El resultado principal tendrá relación con los distintos modos de iterar considerando en cada nodo una función booleana AND u OR. Por último, daremos algunas conclusiones y problemas abiertos. El trabajo aquí expuesto ha permitido una publicación en Theoretical Computer Science llamado The complexity of Bootstrapping Percolation [10], una charla invitada (Winter FRAC 2012, París), una conferencia invitada (CA2012 Córcega), un artículo actualmente enviado a Advances in Applied Mathematics y otro en desarrollo.