Solución al problema P vs NP?

La complejidad computacional es la rama de la computación que estudia la clasificación de los problemas computacionales de acuerdo a su dificultad y los recursos computacionales necesarios para resolverlos. Trata de clasificar los problemas que pueden o no pueden ser resueltos con una cantidad determinada de recursos.

Los recursos computacionales más utilzados son cuántos pasos y cuanta memoria son necesarios para resolver un problema. Como es lógico, no se requiere el mismo número de pasos para factorizar un número entero en sus números primos que para dividirlo por otro entero. En la dificultad para factorizar grandes números enteros reside la clave de los principales algoritmos criptográficos como el RSA.

La clase computacional P contiene a aquellos problemas que se solucionan en tiempo polinómico por una máquina de Turing determinista. Es decir, el número de pasos del algoritmo para resolver el problema está acotado por un polinomio en n, donde n es la longitud de la entrada.

La clase NP contiene los problemas cuya solución se verifica en tiempo polinómico. Este es el tipo de problemas en los que no podemos evitar la fuerza bruta para su resolución y no se conocen algoritmos que los resuelvan en tiempo polinómico. Un subconjunto importante de NP es la clase NP-completo, tal que todo problema en NP se puede reducir a un problema de NP-completo.

Por ejemplo el problema del clique, que trata de determinar cuándo un grafo contiene un clique (subgrafo con todos sus vértices conectados) de al menos tamaño k, es un problema en NP-completo.

Uno de los problemas centrales de la teoría de computación es si P=NP, es decir, si para un problema cuya solución se verifica en tiempo polinómico también se puede encotrar una solución en tiempo polinómico. Incluso el Clay Mathematics Institute ha ofrecido un premio de un millón de dólares estadounidenses para quien desarrolle la primera demostración correcta.

Inclusión de clases de complejidad computacional en función de si P=NP

Inclusión de clases de complejidad computacional en función de si P=NP

Pues bien, Norbert Blum, de la Universidad de Bonn, ha publicado recientemente un artículo donde dice haber resuelto el problema. 

Norbert Blum argumenta que la mejor red booleana monotona para resolver el problema del clique está acotada exponenancialmente por abajo y que ese límite también aplica a las redes no monótonas. Eso implicaría que P≠NP  según él. Ya han salido diversos científicos cuestionando su forma de demostrar el problema, como John Baez. ¿Se habrá demostrado esta vez la gran cuestión?

Actualización Septiembre 2017: Blum intenta extender la cota inferior de complejidad de los circuitos monótonos a los circuitos generales. Para ello usa unos métodos de aproximación que ya fueron descartados hace muchos años. Y sobre todo, está el problema del “perfect matching”, que tiene un circuito monótono con cota inferior exponencial y un circuito general con cota superior polinómica.

La prueba de Blum ha recibido varias críticas de especialistas en complejidad computacional. Finalmente, en la página donde colgó el artículo ha indicado que la prueba no es correcta y que con el tiempo dará más detalles. Aunque no se haya resuelto el problema, sin duda el trabajo de Blum es una gran aportación.

 

 

Anuncios

2 comentarios en “Solución al problema P vs NP?

  1. Enhorabuena, lo explicas mejor que nadie. Creo que existe una confusión garrafal en este asunto, por lo menos en lo que respecta a la demostración de Blum. Todo el mundo se centra en decir que si la función cliqué es superpolinómica ya esta demostrado. Eso no es suficiente, tiene que demostrar que esa función además es la mejor función que resuelve el problema cliqué. También vale que dado un cliqué y obtenida su solución por fuerza bruta se obtenga su función normal disyuntiva (DNF) o conjuntiva (CNF) incluyendo negaciones. Si la mayor simplificación posible de esa función tiene una longitud que crece exponencialmente (o suprapolinomial) se demostraría que P!=NP. La técnica de Blum es demostrar que una función (DNF/CNF) conocida de tamaño suprapolinomial es irreductible en base a una función de reducción; algo así como que aplicando la reducción recursiva a la propia función el tamaño llega a un limite inferior en el que no se reduce más. Esto parece haberlo logrado reviviendo una técnica olvidada hace dos décadas. Lo que a mi me parece no estar demostrado en esta técnica es que la función de reducción (aproximación de Razborov) sea infalible. El propio Razborov parece tener claro que no vale, según dicen por ahí. Hay un contraejemplo de Tardos (al que él mismo hace referencia en su paper) que parece invalidar el método de Razborov de aproximación.

    Me gusta

    • Gracias a ti por la aportacion. Como bien dices, la clave es la aproximacion de Razborov utilizada por Blum y si esta es suficiente para extender la cuota inferior de complejidad de un circuito monotono a uno general. Algunos la estan cuestionando. Un saludo

      Me gusta

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s