problemas NP-intermedios
question: ¿Cuál es el nombre de un problema que cumple con la afirmación de Ladner?, 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.
¿Cuál es el nombre de un problema que cumple con la afirmación de Ladner?
Tales problemas se llaman problemas NP-intermedios .
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.
Tales problemas se llaman <hl> problemas NP-intermedios <hl> .
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 <hl> problemas NP-intermedios <hl>. 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.
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 . <hl> 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.