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 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 para quien desarrolle la primera demostración correcta.
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 especialistas 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.
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.
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
Hi there! This is my first comment here so I just wanted to give a quick shout out and tell you I genuinely enjoy reading your
articles. Can you suggest any other blogs/websites/forums that cover the same topics?
Thank you!
Thanks for this post, I am a big fan of this site
would like to keep updated.
I absolutely love your blog and find most of your post’s to be what precisely I’m looking for. Do you offer guest writers to write content for you personally? I wouldn’t mind publishing a post or elaborating on many of the subjects you write concerning here. Again, awesome website!|