En una de estas calurosas tardes de verano me encontraba yo holgazaneando y haciendo limpieza de contactos de MSN (Dè.ésiH, me pregunto qué extraña enfermedad mental me llevó a agregarte 6 años ha). De repente, en el grupo "Companys universitat" veo uno de los ya licenciados con el siguiente y misterioso nick: "Theorem 7. P!=NP".
"¿Cómo?", pensé mientras me comía el último trozo de melocotón que había cortado con cariño mi madre, y eso mismo le pregunté a este compañero, "¿esto no era un problema del milenio?".
Bueno, me estoy cansando del estilo literario, se me hace cansino y pedante así que al grano voy xD.
La cuestión es que este compañero me explicó que hay todos los años varias demostraciones, pero un empleado de HP, un tal Deolalikar, había desarrollado una demostración que parecía correcta (aún está en proceso de revisión). Yo no sé mucho de complejidad, calculabilidad, teorías del lenguaje y todo eso, es más de informáticos y aunque en matemáticas hay la rama de lógica, de momento yo estoy con Russell, Gödel y sus impresionantes avances, pero para ponernos en situación, la cosa va así:
Hay problemas (teoremas, fórmulas, algoritmos, como queráis llamarlo) que se resuelven en un cierto número de pasos en función del número de elementos del lenguaje (o el número de dígitos por ejemplo en encriptación, o de ciudades en el caso del problema del viajante) - que alguien me corrija si miento- y se dividen en dos tipos. El primero es P (tiempo polinómico), básicamente el número de pasos es una función polinómica (o de menor orden) del número de elementos, es decir que si por ejemplo yo tardo 4 segundos con 2 elementos, a lo mejor con 3 elementos tardaré 9 segundos. Esto es bueno, porque es controlable, y bueno aquí de nuevo los amigos informáticos lo sabrán mejor. El segundo es NP (no polinómico), es decir, a lo mejor con 5 digitos tardamos 4 días y con 6 necesitamos 10 semanas.
Pues bien, allá en el año 1971 un tal Levin dijo que si alguien demostraba que se podía pasar de problemas NP a problemas P (fijaos que el cambio sería radical), o bien lo contrario, se le pagarían 1 millón de $. Es decir, uno de los famosos problemas del milenio. Y ahora este Deolalikar sacó una demostración que parece que si no es correcta, poco le falta, de que no se puede pasar.
Como veis mi conocimiento sobre el tema es prácticamente nulo, pero siempre me ha interesado y como sé que aquí en el foro hay muchos informáticos, proyectos de informático y gente lista en general (CI > 160 oc) digo, pues a lo mejor a alguien le interesa la noticia, y mejor aún, le interesa explicarnos un poco con más detalle la situación xD.
No tengo tiempo de redactar más pero he estado leyendo estos links:
wiki Deolalikar
P=NP=WTF?¿
P versus NP. ¿Nunca lo entendiste?
Y creo que son interesantes para entenderlo un poco y tal, a lo mejor me están timando porque como ya os digo, no tengo ni zorra idea xD.
Bueno, y para acabar y hacer alguna pregunta (a parte de pedir ayuda a los expertos para que completen la poca información que he dado), suponiendo que esta demostración no es correcta, vosotros "creéis" (porque hasta que no esté demostrado, es un acto de fe) ¿que P=NP, que P!=NP? ¿Que son teoremas indecidibles? ¿Que soy un pesado?
Saludos
Corrijo cosas que han comentado otros users con más dominio:
Los problemas P son todos aquellos cuya solución es verificable por una Máquina de Turing determinista mientras que aquellos NP son verificables por una MT no determinista. Esto es, aquellas Máquinas de Turing que en un estado y con la lectura de un símbolo pueden llevar a un estado u a otro.
