Si bien su terminología es imprecisa, cuando se interpreta adecuadamente, la respuesta es no.
En teoría de la complejidad, hay 3 clases de problemas de decisión relativamente fáciles de entender:
P consiste en problemas para los cuales se conoce un algoritmo de tiempo polinómico.
- ¿Cuál es la conexión entre la teoría de conjuntos avanzada (es decir, la que involucra los axiomas cardinales grandes) y el resto de las matemáticas?
- ¿Qué tan bueno debo ser en matemáticas para aprender econometría?
- ¿Cuáles son las aplicaciones de la vida real de la serie Fibonacci?
- ¿Tiene n ^ 2n siempre el último dígito equivalente al último dígito de n en alguna base (como la base 2,3,4,6,12, etc.)?
- ¿Cuál es el plan de estudios que debe seguir un estudiante universitario en el MIT para graduarse con un título de matemática pura?
NP consiste en problemas en los que existe un algoritmo de tiempo polinómico para verificar un certificado que afirma la verdad del problema de decisión.
NP-complete consiste en los problemas de NP “más difíciles”. Esencialmente, si un problema de NP completo admite una solución en tiempo polinómico, entonces cualquier otro problema de NP puede resolverse también en tiempo polinómico.
Primero pregunta si tal algoritmo para encontrar divisores resolvería el “problema de factorización”. La respuesta a esto es sí si todo se indica correctamente. De hecho, declarado como un problema de decisión, el problema de factorización es exactamente determinar si un número [math] n [/ math] tiene un divisor de tamaño como máximo [math] k [/ math].
Sin embargo, su línea final “y, por lo tanto, la prueba para P = NP” no es lógicamente correcta. La razón de esto es que el problema de factorización está en NP, pero no se sabe que esté en NP completo. No hay pruebas conocidas de que la factorización sea tan difícil como algunos problemas difíciles conocidos. En particular, es posible que se pueda lograr la factorización de tiempo polinomial, pero eso sigue siendo P! = NP.
