La única intuición que tenemos para esto es el hecho de que muchas personas lo han intentado pero no han logrado producir una reducción que completa el factoring NP. Por supuesto, esto no significa que la factorización no sea NP completa.
Hay otro problema interesante llamado isomorfismo gráfico, en el que observa dos gráficos y decide si se ven iguales simplemente cambiando el nombre de los vértices. Si este problema resultó ser NP-completo, se sabe que la jerarquía polinómica colapsará. Hay buenas razones para creer que la jerarquía polinómica no colapsa.
Si la factorización resultó ser NP-completa, entonces tendríamos [math] NP \ subseteq BQP [/ math], es decir, NP puede resolverse mediante un algoritmo cuántico aleatorio de error acotado. Hay buenas razones para creer que esto tampoco es cierto.
- ¿Por qué Python es realmente más lento en algunos cálculos que Java? Las profundidades recursivas también son limitadas.
- ¿Cuál es la necesidad de estructuras de datos? ¿Por qué aprendemos estructuras de datos y algoritmos?
- ¿Deberíamos usar un árbol rojo-negro con más frecuencia para abordar los problemas de integridad de NP? ¿Es esto cierto?
- ¿Cómo se puede resolver el coeficiente binomial usando programación dinámica y tabla hash?
- ¿Cuál es la complejidad temporal del algoritmo de búsqueda binaria?
Finalmente, se sabe que si [math] P \ neq NP [/ math], entonces debe haber un lenguaje en NP que no sea NP-complete. Muchas personas creen que el factoring y el isomorfismo gráfico son los candidatos para esto.
