NeoFronteras

¿Es P no igual a NP?

Área: Matemáticas — jueves, 12 de agosto de 2010

Un investigador dice haber demostrado que los problemas tipo NP no pueden ser equivalentes a problemas tipo P.

Foto

¿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

Fuentes y referencias:
Noticia en Nature.
Artículo en ArXiv.
Artículo en ArXiv.

Salvo que se exprese lo contrario esta obra está bajo una licencia Creative Commons.
Compartir »

4 Comentarios

  1. miquel:

    Fantastica entrada.
    Se nota que no estas de vacaciones y que estas al filo de lo que sucede ahi fuera!. Gracias por tu dedicacion.

  2. lluís:

    Pues según el trabajo de LLoyd sobre máquinas del tiempo sin paradoja del abuelo, por medio de la postselección, parece ser que los problemas del tipo NP, podrian ser resueltos de forma rápida y sencilla.Aunque en la propia entrada del estudio de LLoyd se afirma que el tema de la postselección es controvertido.
    De todos modos todo lo que ponga límites al conocimiento me disgusta (aunque pueda ser realista, como por ejemplo el principio de Heisenberg, o la teoría del caos, o el problema de la incomplitud de la matemática de Gödel).

  3. Robert Smith:

    Os recomiendo leer el artículo de New Scientist titulado “Tide turns against million-dollar maths proof”

    http://www.newscientist.com/article/dn19313-tide-turns-against-milliondollar-maths-proof.html

    Saludos,
    Bob

  4. A. K. A.:

    Sólo un par de alcances, encontré algo confusa la explicación de np-completitud para un público en general, que puede llevar a mal entender algunos conceptos, cuando hablamos de np-(completitud) estámos en ámbitos de decibilidad(decidible o Turing-decidible), no de operabilidad (para éstos hay una denominación de npo-completitud, no precisamente de operatoria sino de optimización). El problema de la factorización de números primos así como el del logaritmo discreto aún no son demostrados como np-(completos). Los sistemas de cifrado, son solo seguros dada su intratabilidad,y no por su naturaleza como lo es por ejemplo la criptografía cuántica. Creo que el intento de “D.” se puede sumar a una lista de muchos borradores, que intentan resolver esta pregunta utilizando un problema de prueba, las que por cierto, en poco tiempo son desechadas por su falta y/o carencias de generalidad teórica.

RSS feed for comments on this post.

Lo sentimos, esta noticia está ya cerrada a comentarios.