Todos los problemas en P también están en NP, porque P está contenido en NP. Por otro lado, no se ha demostrado que haya problemas de NP completo en P. Si hubiera uno, todos lo serían, y P sería igual a NP. Por otro lado, hubo al menos un problema NP-intermedio, el isomorfismo gráfico, que recientemente se demostró que estaba en tiempo cuasi polinomial O (n ^ polylog (n)), que no es P, pero está cerca. En general, no hay un montón de problemas que se sabe que están en NP mientras no están completos en NP O están en P (estos se conocen como NP intermedios), por lo que es raro encontrar una solución de tiempo poli para uno.
Una reflexión más: esto se está alejando de la pregunta, pero se relaciona con la última oración de lo que dije anteriormente. Si permite el cálculo cuántico, ha habido problemas NP-intermedios que se encontraron en NP∩BQP (por ejemplo, factorización y registro discreto) y, por lo tanto, manejables en una computadora cuántica, pero eso no es lo mismo que estar en pags.
Actualización: Babai ha retractado parte del resultado del isomorfismo gráfico, ya no se cree que sea cuasi polinomial.
- Criptografía: ¿Cuáles son las ventajas y desventajas de AES sobre Triple-DES?
- ¿Es mejor ingresar a Jadavpur CS o dejar un año para IIT?
- En inglés simple, ¿cómo funciona SSL y cómo es seguro?
- Cómo saber si un puerto USB es 3.0 o no
- Como aspirante a econométrico, ¿debería aprender el aprendizaje automático?
