PUBLICIDAD
Futurama: Put Your Head On My Shoulder
El investigador Vinay Deolalikar de HP Labs afirma tener la prueba de que P ≠ NP en un documento de 100 páginas. Aunque la demostración aún no ha sido revisada por expertos, si resulta válida estaríamos frente al segundo Problema del Milenio resuelto.
Hasta el momento se ha resuelto uno de los 7 problemas (la llamada conjetura de Poincaré) por el ruso Grigori Perelmán, quién recientemente rechazó el premio de USD$1.000.000 que otorga el Clay Mathematics Institute a quienes resuelven estos problemas.
En la teoría de la complejidad computacional el problema “P versus NP” consiste en saber que, si para una máquina es posible “verificar” rápidamente soluciones positivas a un problema del tipo SI/NO (donde “rápidamente” significa “en tiempo polinómico“), es que entonces también se pueden “obtener” las respuestas (si o no) rápidamente.
PUBLICIDAD
P es la clase de problemas cuya solución puede encontrarse en Tiempo polinómico (tiempo de ejecución de un algoritmo). NP es la clase de problemas cuya solución puede verificarse en tiempo no polinomial. Naturalmente, cualquier problema en P también se encuentra en NP. La cuestión P versus NP es si NP está en P y si las clases son iguales. Se puede ver esta cuestión como un caso específico del problema de probar límites inferiores de costos para problemas computacionales.
Si las clases son iguales entonces podemos resolver muchos problemas que actualmente consideramos intratables. Si no, entonces los problemas NP-completos son probablemente problemas NP-hard (o NP-complejo, o NP-difícil). Deolalikar en su documento afirma demostrar que P ≠ NP, lo que significa que hay problemas que se pueden verificar en tiempo no-polinomial pero NO pueden ser resueltos en tiempo polinomial.
En todo caso, lo importante es que se habría resuelto este problema, considerado una de las preguntas abiertas más importantes de la matemática.
XKCD: NP-Completos
Links:
– Claimed Proof That P != NP (Slashdot)
– El estado actual del problema P distinto de NP (Francis thE mule Science’s News)
– P versus NP (Wikilingue)
