| Property |
Value |
| dbo:abstract
|
- El problema del isomorfismo gráfico es el problema computacional para determinar si dos gráficos finitos son isomórficos. No se sabe que el problema se pueda resolver en tiempo polinomial ni que sea NP-completo y, por lo tanto, puede estar en la clase de complejidad computacional NP-intermedia. Se sabe que el problema de isomorfismo gráfico está en la'jerarquía baja de la clase NP, lo que implica que no es NP completo a menos que la jerarquía de tiempo polinomial colapse a su segundo nivel. Al mismo tiempo, el isomorfismo para muchas clases especiales de gráficos se puede resolver en tiempo polinomial, y en la práctica el isomorfismo gráfico a menudo se puede resolver de manera eficiente. Este problema es un caso especial del problema de isomorfismo subgráfico' que pregunta si un gráfico dado G contiene un subgráfico que es isomorfo a otro gráfico dado H y que se sabe que es NP-completo. También se sabe que es un caso especial del problema del subgrupo oculto no abeliano sobre el grupo simétrico. En el área de reconocimiento de imágenes se conoce como la coincidencia gráfica exacta. (es)
- El problema del isomorfismo gráfico es el problema computacional para determinar si dos gráficos finitos son isomórficos. No se sabe que el problema se pueda resolver en tiempo polinomial ni que sea NP-completo y, por lo tanto, puede estar en la clase de complejidad computacional NP-intermedia. Se sabe que el problema de isomorfismo gráfico está en la'jerarquía baja de la clase NP, lo que implica que no es NP completo a menos que la jerarquía de tiempo polinomial colapse a su segundo nivel. Al mismo tiempo, el isomorfismo para muchas clases especiales de gráficos se puede resolver en tiempo polinomial, y en la práctica el isomorfismo gráfico a menudo se puede resolver de manera eficiente. Este problema es un caso especial del problema de isomorfismo subgráfico' que pregunta si un gráfico dado G contiene un subgráfico que es isomorfo a otro gráfico dado H y que se sabe que es NP-completo. También se sabe que es un caso especial del problema del subgrupo oculto no abeliano sobre el grupo simétrico. En el área de reconocimiento de imágenes se conoce como la coincidencia gráfica exacta. (es)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| dct:subject
| |
| rdfs:comment
|
- El problema del isomorfismo gráfico es el problema computacional para determinar si dos gráficos finitos son isomórficos. No se sabe que el problema se pueda resolver en tiempo polinomial ni que sea NP-completo y, por lo tanto, puede estar en la clase de complejidad computacional NP-intermedia. Se sabe que el problema de isomorfismo gráfico está en la'jerarquía baja de la clase NP, lo que implica que no es NP completo a menos que la jerarquía de tiempo polinomial colapse a su segundo nivel. Al mismo tiempo, el isomorfismo para muchas clases especiales de gráficos se puede resolver en tiempo polinomial, y en la práctica el isomorfismo gráfico a menudo se puede resolver de manera eficiente. (es)
- El problema del isomorfismo gráfico es el problema computacional para determinar si dos gráficos finitos son isomórficos. No se sabe que el problema se pueda resolver en tiempo polinomial ni que sea NP-completo y, por lo tanto, puede estar en la clase de complejidad computacional NP-intermedia. Se sabe que el problema de isomorfismo gráfico está en la'jerarquía baja de la clase NP, lo que implica que no es NP completo a menos que la jerarquía de tiempo polinomial colapse a su segundo nivel. Al mismo tiempo, el isomorfismo para muchas clases especiales de gráficos se puede resolver en tiempo polinomial, y en la práctica el isomorfismo gráfico a menudo se puede resolver de manera eficiente. (es)
|
| rdfs:label
|
- Problema del isomorfismo de grafos (es)
- Problema del isomorfismo de grafos (es)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
