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 decidir si la inclusión entre las clases de complejidad P y NP es estricta.
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.
