Programación celular resolución eficiente de problemas numéricos NP-completos

Abstract

Esta memoria está estructurada en capítulos cuyos contenidos pasamos a describir sucintamente.

En el Capítulo 1 se hace una breve introducción histórica de la Teoría de la Computabilidad, analizándose las limitaciones y potencia de los modelos que formalizan el concepto de procedimiento mecánico, así como de la Teoría de la Complejidad Computacional, justificándose la necesidad de estudiar nuevos modelos de computación a fin de mejorar la resolución cuantitativa de problemas matemáticos especialmente difíciles, desde el punto de vista de esta teoría. También se describen brevemente nuevos modelos de computación inspirados en la forma en que la Naturaleza calcula.

El Capítulo 2 está dedicado a la presentación del marco general en que se va a desarrollar esta memoria, la Computación celular con membranas. Concretamente se describen de manera informal los sistemas P de transición, que es el modelo considerado por Gh. Păun en el artículo fundacional de la disciplina. A continuación, se introducen los sistemas celulares reconocedores, que son dispositivos computacionales en el marco de la computación celular con membranas, especialmente adecuadas para reconocer lenguajes y, en consecuencia, para resolver problemas de decisión.

Finalmente, se define una clase de complejidad polinomial que proporciona un concepto de resolubilidad eficiente de problemas a través de sistemas celulares reconocedores; es decir, un concepto de tratabilidad en este nuevo marco no convencional. Esta clase se sitúa por el momento a nivel teórico ya que, como hemos dicho, aún no existen implementaciones en soporte electrónico ni bioquímico.

A menos que P = NP, para atacar de manera eficiente la resolubilidad de problemas NP-completos es necesario disponer de mecanismos que permitan fabricar una cantidad de espacio de tamaño exponencial en tiempo polinomial. Los sistemas celulares con membranas activas son una variante de modo de computación con membranas que satisface este requisito.

En el Capítulo 3 se presenta una formalización de estos sistemas celulares que, en su versión de reconocedores, serán usados a lo largo de la memoria para resolver problemas NP-completos, de manera eficiente, en el marco de la clase de complejidad antes mencionada. En concreto, todas las computaciones de los sistemas diseñados paran y, además, lo hacen tras un número de pasos celulares de orden lineal.

Los Capítulos 4, 5 y 6 están dedicados al estudio de soluciones eficientes de tres problemas numéricos NP-completos: Subset Sum, Knapsack y Partición, a través de sistemas celulares reconocedores con membranas activas. En todas las soluciones se sigue una misma estructura:

- En primer lugar, se presentan los diseños de las correspondientes familias de sistemas celulares.

- A continuación, se realiza una breve descripción intuitiva del funcionamiento de los mismos.

- Finalmente, se demuestra la verificación formal de las soluciones, de acuerdo con la definición de clases de complejidad dada en el Capítulo 2.

Además, al final del Capítulo 6 se incluyen una serie de comentarios en la línea de minimizar los recursos que emplean los sistemas utilizados. Se indica que es posible reducir en uno el número de cargas eléctricas distintas que se admiten. Más concretamente, en los sistemas P con membranas activas se considera que las membranas pueden tener carga positiva, negativa o neutra, pero se muestra que basta considerar solo dos cargas para poder obtener soluciones celulares eficientes.

En las soluciones presentadas en los Capítulos 4, 5 y 6 de los problemas antes citados, se ha observado grandes similitudes entre los diferentes diseños. Ello, unido a las enormes dificultades que existen a la hora de diseñar dispositivos computacionales en los modelos de computación orientados a máquinas (como es el caso de los sistemas P), hace que adquiera especial relevancia la búsqueda de subrutinas que agrupen conjuntos de reglas de evolución de los sistemas, del tal manera que puedan ser utilizadas a modo de instrucciones de un lenguaje de programación celular. Este es el objetivo fundamental del Capítulo 7: la idea de un lenguaje de programación celular es factible, al menos para cierta clase relevante de problemas NP-completos, y podría ser de utilidad a la hora de diseñar y verificar soluciones para nuevos problemas en el futuro.

En el Capítulo 8 se presenta un simulador de sistemas celulares, escrito en Prolog, que permite realizar simulaciones de las soluciones celulares presentadas en los capítulos anteriores. Se trata de una simulación secuencial, ya que en un ordenador convencional no se puede implementar la creación de un espacio de trabajo de tamaño exponencial en tiempo polinomial que llevan a cabo, a nivel teórico, los sistemas P con membranas activas. Conviene aclarar que el simulador no ha sido diseñado específicamente para las familias de sistemas P reconocedores presentadas en esta memoria, sino que ha sido para poder simular cualquier sistema P con membranas activas.

A la hora de analizar soluciones de dispositivos computacionales en el marco de la complejidad computacional, se estudian, básicamente, los recursos en tiempo y/o en espacio utilizados. Pero estas medidas de complejidad pueden resultar claramente insuficientes cuando se trabaja con sistemas celulares con membranas activas que permiten la división de membranas en un paso de transición. En el Capítulo 9 se estudia la necesidad de profundizar en el estudio de nuevos parámetros que permitan analizar la complejidad de los sistemas P como dispositivos computacionales que resuelven problemas de decisión. Esos parámetros pueden orientar al usuario en la tarea de diseñar mejores sistemas que resuelven un mismo problema.

La memoria concluye detallando algunas conclusiones que se pueden extraer de los resultados obtenidos, y se presentan una serie de objetivos y trabajos futuros que marcan nuevas líneas de investigación en modelos de computación no convencionales, algunas de las cuales han comenzado a desarrollarse en colaboración con algunos miembros del grupo de investigación en Computación Natural de la Universidad de Sevilla.