El problema no resuelto más obvio en informática es el problema P = NP.
Hablando en términos generales, “P” son problemas que son fáciles de resolver. (el número de operaciones es menor que alguna función polinómica del tamaño del problema).
“NP” son problemas que son fáciles de verificar la respuesta.
- ¿Hay algún número que el binario no pueda producir?
- ¿Cómo se puede calcular la mediana de una gran variedad de enteros sin mantener todos los valores en la memoria?
- ¿Cuál es la licencia del algoritmo de agrupación combinatoria multiescala?
- Cómo encontrar el número de subárboles izquierdo y derecho de un árbol binario
- Un árbol binario completamente equilibrado tiene 187 hojas. ¿Cuál es la altura del árbol?
Por ejemplo, resolver un problema de Sudoku n-by-n es NP, porque es fácil verificar la respuesta. Es P? Nadie sabe. Nadie ha encontrado un algoritmo para hacerlo, y nadie ha encontrado una prueba de que sea imposible.
Hay cientos de problemas que son claramente NP, pero nadie sabe si son P. Muchos de estos problemas tienen aplicaciones logísticas del mundo real. (Por ejemplo, determinar la mejor manera de cargar un camión con paquetes o romper el cifrado RSA)
De hecho, nunca se ha demostrado que ningún problema de NP sea P.
Aquí está la parte extraña: si Sudoku es P, entonces todos los problemas de NP son P. Eso es correcto: si hay un algoritmo “fácil” para resolver un Sudoku n-by-n, entonces el cifrado RSA puede romperse.
Esta propiedad de Sudoku se llama “NP-complete”. Hay cientos de problemas NP-completos conocidos. Si alguno de ellos es P, entonces todos los problemas de NP son P. Y si incluso un solo problema de NP es “difícil”, entonces todos los problemas de NP completo son “difíciles”.
Se ofrece un premio de $ 1 millón por una respuesta a esta pregunta.
Problemas del Premio del Milenio
