Menú

Máquinas inspiradas en la naturaleza viva (I)

21 de marzo de 2007

Detrás del título de esta conferencia que impartió Mario de J. Pérez Jiménez el miércoles 7 de marzo, nos encontramos con uno de los aspectos más apasionantes de la computación. Y si además quien habla de ello es este profesor del departamento de Ciencias de la Computación e Inteligencia Artificial mucho mejor. Tuve el honor de tenerlo en la asignatura Computabilidad y Complejidad el pasado cuatrimestre y verdaderamente es un hombre que contagia su ímpetu y sus ganas de aprender y seguir investigando. Su conferencia, sobre computación natural, fue densa, llena de conceptos, pero todo ello necesario para comprender en qué consiste su actual línea de investigación.

Y es que estamos hablando del que sea posiblemente el problema matemático más importante del milenio: La conjetura P=NP. De hecho, este problema es el primero de la lista que el Instituto Clay de Matemáticas (Cambridge, Massachusetts) elaboró, premiando con un millón de dólares a aquél que sea capaz de resolver alguno de ellos. Como curiosidad, tan sólo uno ha sido resuelto por ahora, la conjetura de Poincaré (ahora ya teorema), hace sólo algunos meses. Pero cuando la conjetura P=NP está la primera en la lista es sin duda por algo. Y es que la demostración de ésta llevaría consigo muchísimas cosas, y entre ellas la posibilidad de resolver los 5 restantes problemas.

¿Pero en qué consiste esta igualdad? ¿Qué es P y qué es NP?

Bueno, ambas son clases de complejidad, es decir, conjuntos de problemas de decisión (con decisión me refiero a que su solución es una afirmación o una negación, un o un no, un 1 ó un 0) que guardan unas propiedades comunes:

  • La Clase P es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista (o el equivalente a un ordenador convencional) en tiempo polinomial. Lo de determinista quiere decir que a valores iguales de entrada, el resultado siempre será el mismo. Esto es fácil de entender si alguna vez has hecho una función o un método en algún lenguaje de programación. Si llamas 2 veces a alguna de tus funciones con los mismos argumentos de entrada, el resultado será el mismo.
  • La Clase NP es el conjunto de problemas resolubles por una máquina de Turing no determinista en tiempo polinomial. Una máquina de Túring no determinista es áquella que posee varias computaciones diferentes para una misma entrada.

Hay que aclarar que la potencia de una MTD es la misma que la de una MTND. Ambas son capaces de resolver los mismos problemas. Su diferencia reside en la eficiencia. Y esta eficiencia es la que trae de cabeza a todos los investigadores, pues hay algunos problemas, los de mayor complejidad de la clase NP (los llamados problemas NP-Completos), que al intentar resolverlos con ordenadores convencionales tardan un tiempo exponencial en función del tamaño de la entrada.
Un ejemplo de este tipo de problemas lo encontramos en el Problema del Viajante. En él, un viajante intenta visitar una serie de ciudades conectadas entre sí (imagínense un grafo donde los vértices son las ciudades y las aristas un camino entre dos ciudades) sin pasar 2 veces por ninguna, visitándolas todas y terminando en la ciudad de partida, siendo mínima la distancia recorrida por éste. Si aumentamos el tamaño del grafo (el número de ciudades) el tiempo que tardará un ordenador en resolver el problema, por muy rápido que sea, aumentará exponencialmente, de modo que para valores no muy altos de entrada no hay computadora capaz de devolver una solución.

¿Por qué es tan importante la conjetura P=NP?

Los algoritmos criptográficos, que hacen que la información viaje segura y que nadie no autorizado pueda acceder a cierta información se basan precisamente en el largo tiempo que una máquina tarda en descifrar las claves. Por ejemplo, la seguridad del sistema de encriptación RSA se basa en la imposibilidad de que una máquina tradicional factorice un número grande en factores primos en un tiempo decente. De esta manera la clave de descifrado se mantiene segura.
Pero si la conjetura P=NP fuera cierta, entonces sería posible diseñar un algoritmo que hiciera esto en tiempo polinomial. Hablando claro, podríamos diseñar un decodificador universal, capaz de descifrar cualquier tipo de mensaje encriptado. Además, muchos problemas de la vida real que actualmente no tienen solución por encontrarse frenados por un problema NP-Completo podrían ser resueltos. Los avances en la ciencia serían inimaginables.
Desafortunadamente, aunque aún no está demostrado, todo parece indicar que P es distinto de NP. Si esto es así, el mundo de la computación tal y como la conocemos tiene los días contados. La necesidad de buscar solución a muchos grandes problemas de la vida real ha llevado a crear nuevos modelos de computación alternativos, que se alejan del circuito electrónico que conduce pulsos eléctricos…

Continuará…

5 Comentarios en Máquinas inspiradas en la naturaleza viva (I)

  1. Avatar de <a href='http://www.noseque.net' rel='external nofollow' class='url'>Gosku</a>

    Gosku dice:

    21/3/2007, 17:27

    No soy ningún experto en el tema. Así que espero no haberla cagado con algo de lo que he contado. Si alguien ve algún error en lo que he escrito, por favor, que me lo comunique, por ejemplo, a través del formulario de contacto.

  2. Avatar de krego

    krego dice:

    21/3/2007, 22:17

    Muy interesante. Al final casi introduces la importancia de la computación cuántica pero seguramente lo toques en el siguiente artículo. Te animo a que continues con este tipo de posts.

    Un saludo

  3. Avatar de Pablo

    Pablo dice:

    27/3/2007, 13:29

    Yo tengo unas dudas… si se demostrar que P = NP esto quiere decir que se sabe que se podría resolver “rápidamente”, pero habría que encontrar la solución
    “rápida” a ese problema no? que supongo que podrá ser según el caso muy compleja. Vamos que si se demuestra que P = NP se sabe que es resoluble, pero entonces esta demostración proporcionaría mecanismos para resolver en tiempo polinomial? o no tiene porque? en que medida ayudaría saber que P = NP a resolver problemas NP?

  4. Avatar de <a href='http://www.noseque.net' rel='external nofollow' class='url'>Gosku</a>

    Gosku dice:

    27/3/2007, 17:22

    Bueno, más o menos. Demostrar que P = NP implica demostrar que un problema NP-Completo pertenece a la clase P. A su vez, demostrar que un problema es NP-Completo implica demostrar que es NP, una tarea relativamente sencilla, y además encontrar una aplicación que transforme otro problema NP-completo en ese problema y que corra en tiempo polinomial.

    De modo que si demuestras que un problema NP-Completo pertenece a P a su vez estás demostrando que todos los demás problemas NP-Completos pertenecen a P (pues está demostrado que entre problemas NP-Completos existen reducibilidades en tiempo polinomial). Utilizando estas reducibilidades, teóricamente podrías encontrar soluciones para el resto de problemas NP-Completos que corrieran en tiempo polinomial de una manera relativamente sencilla (para los matemáticos. A mí me resultaría imposible xD).

  5. Avatar de karent borda

    karent borda dice:

    9/4/2008, 03:15

    ahi ustedes no saben ayudar con una marica tarea
    gracias x nada yo necesitaba una maquina creada con inspiracion en la naturaleza no esoo..
    por ejemplo el elicoptero que fue creador insipirado en uan libelula algo asi ok
    estupidos bobos investiguen y ahi si ayuden

Leave a comment