problema del isomorfismo gráfico
question: ¿Cuál es el problema atribuido a definir si dos grafos finitos son isomorfos?, context: El problema del isomorfismo gráfico es el problema computacional de determinar si dos grafos finitos son isomorfos. Un problema importante sin resolver en la teoría de la complejidad es si el problema del isomorfismo gráfico está en P, NP-completo, o NP-intermedio. La respuesta es desconocida, pero se cree que el problema no es NP-completo. Si el isomorfismo de grafos es NP-completo, la jerarquía de tiempo polinomial colapsa a su segundo nivel. Dado que se cree ampliamente que la jerarquía polinómica no colapsa a ningún nivel finito, se cree que el isomorfismo gráfico no es NP-completo. El mejor algoritmo para este problema, debido a Laszlo Babai y Eugene Luks tiene tiempo de ejecución 2O (√ (n log (n))) para grafos con n vértices.
¿Cuál es el problema atribuido a definir si dos grafos finitos son isomorfos?
El problema del isomorfismo gráfico es el problema computacional de determinar si dos grafos finitos son isomorfos.
El problema del isomorfismo gráfico es el problema computacional de determinar si dos grafos finitos son isomorfos. Un problema importante sin resolver en la teoría de la complejidad es si el problema del isomorfismo gráfico está en P, NP-completo, o NP-intermedio. La respuesta es desconocida, pero se cree que el problema no es NP-completo. Si el isomorfismo de grafos es NP-completo, la jerarquía de tiempo polinomial colapsa a su segundo nivel. Dado que se cree ampliamente que la jerarquía polinómica no colapsa a ningún nivel finito, se cree que el isomorfismo gráfico no es NP-completo. El mejor algoritmo para este problema, debido a Laszlo Babai y Eugene Luks tiene tiempo de ejecución 2O (√ (n log (n))) para grafos con n vértices.
El <hl> problema del isomorfismo gráfico <hl> es el problema computacional de determinar si dos grafos finitos son isomorfos.
El <hl> problema del isomorfismo gráfico <hl> es el problema computacional de determinar si dos grafos finitos son isomorfos. Un problema importante sin resolver en la teoría de la complejidad es si el problema del isomorfismo gráfico está en P, NP-completo, o NP-intermedio. La respuesta es desconocida, pero se cree que el problema no es NP-completo. Si el isomorfismo de grafos es NP-completo, la jerarquía de tiempo polinomial colapsa a su segundo nivel. Dado que se cree ampliamente que la jerarquía polinómica no colapsa a ningún nivel finito, se cree que el isomorfismo gráfico no es NP-completo. El mejor algoritmo para este problema, debido a Laszlo Babai y Eugene Luks tiene tiempo de ejecución 2O (√ (n log (n))) para grafos con n vértices.
<hl> El problema del isomorfismo gráfico es el problema computacional de determinar si dos grafos finitos son isomorfos. <hl> Un problema importante sin resolver en la teoría de la complejidad es si el problema del isomorfismo gráfico está en P, NP-completo, o NP-intermedio. La respuesta es desconocida, pero se cree que el problema no es NP-completo. Si el isomorfismo de grafos es NP-completo, la jerarquía de tiempo polinomial colapsa a su segundo nivel. Dado que se cree ampliamente que la jerarquía polinómica no colapsa a ningún nivel finito, se cree que el isomorfismo gráfico no es NP-completo. El mejor algoritmo para este problema, debido a Laszlo Babai y Eugene Luks tiene tiempo de ejecución 2O (√ (n log (n))) para grafos con n vértices.