No
Nadie ha resuelto P vs NP últimamente.
Porque no he oído hablar de Tara Karimi, sin ofender (como eso nunca ayuda).
- ¿Qué nos hace diferentes de los robots biomecánicos?
- ¿Se pueden utilizar los datos de comentarios de Facebook para crear un software que pase la prueba de Turing?
- ¿Cuál es un buen algoritmo para la detección de contexto en chatbots?
- ¿Jack Ma tiene razón al decir que la IA causará más dolor social que beneficios en los próximos 30 años?
- ¿Qué sucede cuando los robots y los sistemas autónomos ocupan completamente sus trabajos? ¿Dónde trabajará la fuerza laboral? ¿Cuál será su papel?
Si alguna vez se resuelve P vs NP, quien lo resuelva se convertirá instantáneamente en la persona más famosa del planeta. Por extensión, el más rico también.
P vs NP
Hablando informalmente, pregunta si cada problema cuya solución puede ser verificada rápidamente por una computadora también puede resolverse rápidamente por una computadora. [1]
Un buen ejemplo es este sobre la selección de dormitorios universitarios para estudiantes, ya que utiliza un escenario bastante simple [2]. Sin embargo, no publicaré todo el muro de texto.
P = NP
Si P es de hecho igual a NP, entonces quizás todos estamos jodidos. La palabra clave es quizás. Pero si alguien prueba P = NP nosotros (desarrolladores de software) estaríamos haciendo cola para tratar de romper la criptografía de clave simétrica y la criptografía de clave pública.
Puede que no sea inmediato, pero eso empeorará las cosas.
Si se puede diseñar un algoritmo eficiente en torno a un problema de NP, entonces la criptografía se descompone y todos tenemos que llevar algo: teclas de millones de bits. Sí, fastidio.
Si el algoritmo es ineficiente y tarda demasiado en computar, entonces ocurre una de dos cosas: obtenemos computadoras más potentes o alguien trabaja lo suficientemente duro como para resolverlo. Incluso si fallan, la paranoia en nosotros nos hará llevar llaves de bits grandes. Y alguien tiene que diseñar un algoritmo para calcular todos los escenarios posibles.
Supongo que dependiendo de quién resuelva esto, podrían decidir mantenerlo en secreto y usarlo para dominar el mundo del mal. O porque sería peligroso publicitarlo.
He visto sus videos de Youtube y también hojeé el periódico. No. P todavía es vs NP.
Notas al pie
[1] Problema P versus NP – Wikipedia
[2] Instituto de Matemáticas Clay