Al parecer un científico de HP acaba de presentar a revisión la demostración de la proposición 'P no es igual a NP', que viene a decir que la clase de complejidad de la resolución de problemas Polinomiales es distinta de la de los No Polinomiales.
Su nombre es Deolalikar Vinay, un investigador de HP, y podría tornarse un millón de dólares más rico si es verdad lo que escribió en su último artículo científico: P ≠ NP!
Ya le han incluso creado una página en Wikipedia, y los wikipedistas están ya, como de costumbre, ferozmente debatiendo si su notabilidad es o no (todavía) suficiente como para estar en la enciclopedia en línea.
Será otro que se equivoca? ¿O esta vez vamos a tener una respuesta definitiva a la pregunta del millón de la Ciencia de la Computación?
En realidad, NP no significa "No Polinomial", sino, "No-determinista Polinomial". Los problemas de la clase NP pueden ser resueltos en tiempo polinomial por una máquina de Turing No-Determinista.
Este tipo de máquina es una construcción mental, y puedes pensar en ella como un tipo de máquina que "magicamente" sabe cuál es la ruta más corta de entre todas sus posibles rutas de ejecución, y esa es la que sigue. O también puedes pensar en ella como una máquina masivamente paralela que puede ejectuar simultáneamente todas sus posibles rutas de ejecución, y detenerse cuando una de ellas finaliza.
El que un problema sea resoluble en tiempo polinomial por una máquina así, a primera vista, no parece gran cosa, ya que la máquina "hace trampa" al seguir siempre la vía más corta. ¡Pero es que hay problemas que ni con una máquina mágica como esa podrían resolverse en tiempo polinomial!
Los problemas tipo P son los que se pueden resolver en tiempo polinomial con una máquina de Turing determinista, o lo que es lo mismo, con cualquier ordenador convencional.
El que P sea diferente de NP significa que los problemas de la categoría NP, no se pueden resolver en tiempo polinomial en una máquina determinista, requieren una no-determinista para ello. Podría parecer que esto pone a salvo los algoritmos criptográficos (que se basan en que los tiempos necesarios para "romper" el código en un computador determinista son prohibitivamente grandes). Sin embargo, no está demostrado que una máquina no-determinista no pueda ser construida. Algunos piensan que la computación cuántica podría crear una máquina así. Si se pudiera construir una máquina así, los problemas NP (entre ellos el "romper" un código criptográfico) podría ser resuelto en tiempo polinomial.
Clases de complejidad P y NP
La relación entre las clases de complejidad P y NP es una pregunta que aún no ha podido ser respondida por la teoría de la complejidad computacional. En esencia, la pregunta ¿es P = NP ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente?
Los recursos comúnmente estudiados en complejidad computacional son:
– El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.
– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.
Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP Completo, NP Duro...).Nosotros nos vamos a centrar en las clases P y NP.
Se lo considera el problema más importante en este campo--el Clay Mathematics Institute ha ofrecido un premio de $1 millón de dólares norteamericanos para quién desarrolle la primera demostración correcta.
No hay comentarios:
Publicar un comentario