El problema P versus NP.
Este problema se origina en una carta escrita por Kurt Godel. El problema pregunta “Si puedo verificar un problema de manera eficiente, ¿puedo también resolverlo de manera eficiente”. Por eficiente, nos referimos a la existencia de un algoritmo informático de tiempo polinómico. Se utiliza una máquina de Turing para modelar el programa.
Varios enfoques para resolver el problema han fallado. Ahora tenemos pruebas de “barreras” contra la prueba. Por ejemplo, la relativización es una barrera. La relativización es la técnica en la que se supone que una operación es libre, por ejemplo, se podría suponer que la operación de raíz cuadrada se libera, no se contarían los pasos realizados. Tenemos una prueba de que si usa la relativización en su prueba, no resuelve P versus NP. Esto se debe a que tenemos A y B de modo que P en relación con A = NP en relación con A y P en relación con B no es igual a NP en relación con B. Hemos realizado muchos avances en la teoría de la complejidad, mientras trabajamos en el problema. Sin embargo, la solución no parece probable.
- ¿Existe un término para funciones paramétricas encadenadas?
- ¿Cuál es la forma de convertir una razón en un porcentaje?
- ¿De qué sirven las matemáticas en las computadoras?
- ¿Qué tipos de matemáticas necesito aprender para entender la teoría de cuerdas?
- ¿Cuál es la aplicación de la serie de Taylor en la vida real?
Es uno de los problemas del Premio Milenio en Matemáticas. Hay más de 3000 problemas completos de NP. La solución a cualquiera de esos problemas significa que todos se resolverán.
Este problema es definitivamente el más grande en la historia de la informática. Si se resuelve este problema, tendrá implicaciones en la Criptografía, ya que la dificultad de Factoring Prime se entenderá correctamente.
