Un investigador dice haber demostrado que los problemas tipo NP no pueden ser equivalentes a problemas tipo P.
|
¿Ha sido resuelto uno de los grandes enigmas de la computación? ¿Es todo problema de tipo NP igual a uno de tipo P? Según un investigador la respuesta es no.
La relación entre las clases de complejidad P y NP es estudiada por la teoría de la complejidad computacional que trata de los recursos (tiempo o memoria) requeridos durante un cálculo para resolver un problema dado. En esta teoría, la clase P contiene aquellos problemas de decisión que pueden ser resueltos con una máquina determinista secuencial (un ordenador) en un período de tiempo polinómico que es proporcional a los datos de entrada. Es decir, que si aumentamos los datos de entrada, el tiempo necesario para resolverlo no crece exponencialmente, sino más ñentamente. Este tipo de problemas son problemas “fáciles” y rápidos de resolver, como ordenar alfabéticamente un conjunto de palabras. Bajo esas mismas condiciones un problema NP no puede ser resuelto en un tiempo polinómico, sino en un tiempo exponencial, aunque sí se podría resolver rápidamente si se cuenta con una máquina (conceptual) no determinista.
Los problemas de tipo P son relativamente fáciles de calcular o al menos no crecen hasta lo imposible en dificultad de cálculo. Los problemas NP crecen en complejidad muy rápidamente y llega un momento en que es imposible obtener la solución óptima (a no ser que estemos dispuestos a esperar mucho tiempo). En este caso nos tendremos que conformar con una aproximación.
El problema del viajante, la factorización de números en primos, el de la mochila y muchos otros son de tipo NP y de alguno de ellos se sospecha que son de tipo NP-completos que son aún más difíciles de resolver. Básicamente este tipo de problemas son problemas en los que hay que probar con todas las combinaciones posibles y sólo la fuerza bruta permite obtener la solución.
La pregunta suege es si todo problema de tipo NP se puede reformular a uno de tipo P, con lo que un problema que sería inabordable pasaría a ser resoluble. Según Wikipedia en una encuesta realizada en el 2002 entre 100 investigadores, 61 creían que la respuesta a esa pregunta era “no”, 9 creían que la respuesta era “sí”, 22 no estaban seguros, y 8 creían que era imposible de demostrar si la respuesta es “sí” o “no”.
Ahora, Vinay Deolalikar, un matemático de Hewlett-Packard Labs en Palo Alto (California) ha enviado un borrador de artículo de unas cien páginas titulado simplemente «P ≠ NP». Con esto opta al premio de un millón de dólares que el Instituto de Matemáticas Clay otorga a los que resuelvan los siente problemas del milenio. Si este investigador está en lo cierto, el resultado tendría grandes implicaciones en ciencias de la computación.
Deolalikar usa en su demostración un problema particular: el problema de la satisfacción booleana, que pregunta sobre si una colección de afirmaciones lógicas pueden ser simultáneamente verdaderas o si hay contradicciones. Es un problema de tipo NP prototípico.
Deolalikar afirma que ha podido demostrar que no hay manera de resolver ese problema en tiempo polinómico y que por tanto no es equivalente a un problema de tipo P. Esto pondría límites a lo que un computador puede resolver e implica que hay ciertas tareas que fundamentalmente tienen una complejidad computacional irreducible.
A los resultados de Turing y Gödel habría que sumar (salvando las distancias) este resultado, pues impondría más límites absolutos al conocimiento. Hay cosas que no podemos saber, no porque seamos tontos, limitados o poco competentes, sino porque no hay manera de saberlo.
En su demostración este investigador usa herramientas prestadas de la Física Estadística y estructuras matemáticas que normalmente se emplean en sistemas físicos desordenados.
Para la subclase de problemas NP-completos este resultado sería una maldición, pues si P ≠ NP, entonces nunca se podrán resolver los problemas NP-completos de un modo satisfactorio y rápido. Sin embargo, es una buena noticia para nuestros sistemas de cifrado (como RSA) que siguen siendo seguros.
Varios expertos están estudiando la demostración y todavía no está claro si es una demostración totalmente correcta. Muchos de los especialistas en el campo confían en que, dada la dificultad del problema y la historia pasada, probablemente esta demostración también contenga alguna contradicción que la invalide.
Copyleft: atribuir con enlace a http://neofronteras.com/?p=3220 [1]
Fuentes y referencias:
Noticia en Nature. [2]
Artículo en ArXiv. [3]
Artículo en ArXiv. [4]