¿Pueden resolverse instancias de SAT mediante autómatas celulares?

Question

Soy estudiante de secundaria y tengo que escribir un trabajo de investigación de 4000 palabras sobre matemáticas (como parte del Programa del Diploma del BI). Entre mis posibles temas estaban los autómatas celulares y el problema de la satisfabilidad booleana, pero entonces pensé que quizá había una conexión entre ambos. Las variables de las expresiones booleanas pueden ser Verdaderas o Falsas; las celdas de los autómatas celulares pueden estar "Encendidas" o "Apagadas". Además, el estado de algunas variables en las expresiones booleanas puede depender del de otras variables (por ejemplo, la salida de una función booleana), mientras que el estado de las celdas en los autómatas celulares depende del de sus vecinas.

¿Sería posible utilizar autómatas celulares para resolver una instancia de satisfacción? Si es así, ¿cómo y dónde puedo encontrar información útil/relevante?

Gracias de antemano.

Answer 1

Si pudieras encontrar una forma eficiente de resolver el SAT, te harías muy rico y famoso. No es probable que eso ocurra cuando aún estás en el instituto. Lo que sí podrías hacer es que tu autómata celular recorriera todos los valores posibles de las variables y comprobara el valor de la expresión booleana para cada uno de ellos.

Answer 2

La respuesta es sencilla: sí. ¿Se puede hacer de forma sencilla? Probablemente no. Cook demostró en 2004 que se puede calcular cualquier cosa que una máquina de Turing pueda hacer con autómatas celulares de elemetría utilizando la regla 110 y una cuidadosa selección de las condiciones de inicio. Sin embargo, es probable que no haya una regla simple o condiciones de inicio para hacer esto.

ver: http://blog.barvinograd.com/2012/11/cyclic-tag-system-1-line-of-turing-complete-code/ para más detalles.