1 de Abril de 2019

• Autor: Orellana Martín, David.
• Titulo: “El Problema P Versus Np. Desarrollo de Nuevas Técnicas a través de Modelos de Computación Bio-Inspirados”
• Departamento: Ciencias de la Computación e Inteligencia Artificial.
• Teseo: https://www.educacion.gob.es/teseo/mostrarRef.do?ref=1751979
• Directores: Mario de Jesús Pérez Jiménez y Luis Valencia Cabrera (Codirector).
• Sinopsis:

  Desde la aparición de los primeros modelos de computación en la década de los treinta del pasado siglo, han surgido nuevos modelos inspirados en fuentes muy diversas, en particular en procesos de la Naturaleza viva. La teoría de la computabilidad es la disciplina científica que estudia la capacidad de los modelos de computación para resolver mecánicamente problemas abstractos. La construcción de las primeras máquinas de propósito general, en la década de los cuarenta del pasado siglo, dio origen al análisis de la capacidad de esas máquinas para resolver instancias de problemas de «gran» tamaño usando una «cantidad razonable» de recursos computacionales, dando origen a la teoría de la complejidad computacional.

  El problema P versus NP (determinar si las clases de complejidad P y NP son iguales) trata de precisar si «es más difícil hallar una solución de un problema que comprobar si una presunta solución es, realmente, una solución correcta del mismo». Este problema es, sin lugar a dudas, el más importante en Ciencias de la Computación y uno de los más relevantes que tiene planteada la Ciencia, en general. Con el fin de «dar la bienvenida a las Matemáticas del nuevo milenio», el Clay Mathematics Institute (CMI) de Cambridge, Massachusetts (USA), seleccionó siete problemas de especial relevancia (entre los que se encuentra el problema P versus NP), ofreciendo una dotación de un millón de dolares para aquel que resolviera alguno de ellos. La solución de dicho problema tendría unas repercusiones extraordinarias, especialmente desde el punto de vista económico, tanto en lo que respecta a la seguridad de los actuales sistemas de cifrado (RSA, DES, etc.), como a la posibilidad de construir un decodificador universal; es decir, una máquina capaz de romper, en tiempo record, los textos cifrados por los actuales sistemas de cifrado.

  En esta tesis se presenta una nueva metodología para abordar la resolución del problema antes citado, desde una perspectiva completamente novedosa, basada en la obtención de fronteras entre la no eficiencia y la presumible eficiencia de un modelo de computación arbitrario. La metodología desarrollada es aplicada, específicamente, a dispositivos computacionales en el paradigma de la Computación Celular con Membranas.