En la tarde del 4 de mayo de 1971, en Stouffer Somerset Inn en Shaker Heights, Ohio, Steve Cook presentó su documento de STOC demostrar que satisfacibilidad es NP-completo y la tautología es NP-duro.
Hace 40 años hoy, Cook presentó su ponencia sobre el problema que hoy conocemos como la " P vs NP "problema, o la hipótesis de" P = NP ".
Desde el enlace de wikipedia: "Supongamos que las soluciones a un problema se puede verificar rápidamente Entonces, las soluciones se pueden también calcular rápidamente.?" Si usted puede contestar a esta pregunta, obtendrá un millón de dólares del Instituto Clay y un montón de elogios.
Algunos problemas interesantes que no se sabe que en P o NP-completo son los problema de la factorización de enteros . Aún así, si resulta que P = NP, entonces vamos a tener que retirarse de cifrado RSA .
( anteriormente , y el fatal defectos en el proyecto de "prueba" )
No hay comentarios:
Publicar un comentario