Ladner
question: ¿Quién demostró que P = NP implica problemas no presentes en P o NP-completo?, context: Ladner demostró que si P ≠ NP entonces existen problemas en NP que no están en P ni en NP-completo. Tales problemas se llaman problemas NP-intermedios. El problema del isomorfismo gráfico, el problema del logaritmo discreto y el problema de factorización de enteros son ejemplos de problemas que se cree que son NP-intermedios. Son algunos de los pocos problemas de NP que no se sabe que están en P o son NP-completos.
¿Quién demostró que P = NP implica problemas no presentes en P o NP-completo?
Ladner demostró que si P ≠ NP entonces existen problemas en NP que no están en P ni en NP-completo.
Ladner demostró que si P ≠ NP entonces existen problemas en NP que no están en P ni en NP-completo. Tales problemas se llaman problemas NP-intermedios. El problema del isomorfismo gráfico, el problema del logaritmo discreto y el problema de factorización de enteros son ejemplos de problemas que se cree que son NP-intermedios. Son algunos de los pocos problemas de NP que no se sabe que están en P o son NP-completos.
<hl> Ladner <hl> demostró que si P ≠ NP entonces existen problemas en NP que no están en P ni en NP-completo.
<hl> Ladner <hl> demostró que si P ≠ NP entonces existen problemas en NP que no están en P ni en NP-completo. Tales problemas se llaman problemas NP-intermedios. El problema del isomorfismo gráfico, el problema del logaritmo discreto y el problema de factorización de enteros son ejemplos de problemas que se cree que son NP-intermedios. Son algunos de los pocos problemas de NP que no se sabe que están en P o son NP-completos.
<hl> Ladner demostró que si P ≠ NP entonces existen problemas en NP que no están en P ni en NP-completo. <hl> Tales problemas se llaman problemas NP-intermedios. El problema del isomorfismo gráfico, el problema del logaritmo discreto y el problema de factorización de enteros son ejemplos de problemas que se cree que son NP-intermedios. Son algunos de los pocos problemas de NP que no se sabe que están en P o son NP-completos.