P=?NP: La encuesta

I have this wonderful proof that P≠NP, but it is too large to write in the margin of this email message!

Si P=NP (y sabemos cómo) es el fin del mundo como lo conocemos. El millón de dólares que ofrece el instituto de matemáticas Clay se vuelve poca cosa comparado con el dinero que se podría producir en puros procesos industriales, ya no se diga ahorrando en rutas de viaje. Si P≠NP, a simple vista no pasa nada, quedamos con la seguridad de que hay procedimientos que no se pueden realizar de forma práctica en la tecnología actual, seguimos buscando forma de construir máquinas de cómputo no deterministas, y alguien se gana un milloncito (para las pizzas).

Ahí hay una especie de elemento romántico, parecido a la “frontera final” de Viaje a las Estrellas, donde importa más el viaje que el destino. Podría ser que P=NP se vea tan imposible, y que los científicos lo vean con cara de “eso no puede ser” y encuentren, en el subconciente, formas de no resolverlo. O, también, que P≠NP, y entonces la idea de que existe un límite a lo que podemos hacer cause que no se le dedique el esfuerzo que requiere. Porque, ¿qué es un millón de dólares comparado con el sueño de encontrar rutas perfectas con un teléfono celular?

En 1996-7 se recopiló la opinión de 100 científicos de la computación respecto al problema. Las opiniones se dividen como sigue:

5 científicos opinaron que se resolvería entre 2002 y 2009. Otros 5, que ente el 2200 y el 3000. 5 más, que nunca se resolvería.

9 pensaban que P=NP. 57, que P≠NP. 4 pensaron que es independiente del sistema axiomático. 3 afirmaron que no es independiente de la Aritmética Primitiva Recursiva (lo que sea que sea eso). Uno dijo que depende del modelo, y 22 no opinaron.

11 científicos consideraron que se emplearía combinatoria y complejidad para resolverlo. 9 dijeron que se emplearía lógica. 3 mencionaron técnicas algebraicas, uno mencionó técnicas de continuidad, y uno afirmó que es inevitable emplear cohomología de orden superior. Alguien dijo que sería una demostración asistida por computadora (como en el teorema de los cuatro colores). Hubo opiniones para contradicción, inducción, cotas, y la presentación de un algoritmo para un problema NP Completo.

— SIGACT News Complexity Theory Column 36 [PDF]

My hunch is that the problem will be solved by a young researcher who is not encumbered by too much conventional wisdom about how to attack the problem — Richard Karp, Berkeley