| dbo:abstract
|
- Unsolved problem in computer science: Can the graph isomorphism problem be solved in polynomial time? (more unsolved problems in computer science) The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level. At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently. This problem is a special case of the subgraph isomorphism problem, which asks whether a given graph G contains a subgraph that is isomorphic to another given graph H; this problem is known to be NP-complete. It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group. In the area of image recognition it is known as the exact graph matching. (en)
- 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)
- En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. Ce problème est particulièrement important en théorie de la complexité, plus particulièrement pour le problème P=NP. En effet, le problème de l'isomorphisme de graphes est l'un des problèmes de NP, pour lequel on ne connaît ni d'algorithme en temps polynomial ni de preuve de NP-complétude. On le soupçonne être un problème NP-intermédiaire[réf. souhaitée]. Cependant le problème peut être résolu en temps polynomial pour certaines classes de graphes, par exemple les graphes planaires ou les graphes de degré borné et en temps quasi-polynomial pour le cas général. Ce problème peut-être vu comme une restriction du problème de l'isomorphisme de sous-graphes. où les graphes G et H ont le même nombre de sommets. En pratique, l'isomorphisme de graphes est utilisé en chimie pour classer les molécules. (fr)
- O problema de isomorfismo de grafos é um problema computacional para determinar se dois grafos finitos são isomórficos. Não é conhecido se o problema pode ser solucionável em tempo polinomial nem se é NP-completo e, portanto, pode estar na classe de complexidade computacional NP-Intermediário. Sabe-se que o problema do isomorfismo do grafo está na baixa hierarquia da classe NP, o que implica que não é NP-completo a menos que a hierarquia de tempo polinomial colapse para o segundo nível.Ao mesmo tempo, o isomorfismo para muitas classes especiais de grafos pode ser resolvido em tempo polinomial, e na prática o isomorfismo do grafo pode ser resolvido de forma eficiente. Além de sua importância prática, o problema do isomorfismo de grafos é uma curiosidade em teoria da complexidade computacional, uma vez que faz parte de um número muito pequeno de problemas pertencentes a classe NP, conhecidos por não poderem serem resolvidos em tempo polinomial e nem em NP-completo: é um de apenas 12 dos problemas listados por Garey e Johnson (1979) e o único dessa lista cuja complexidade continua não resolvida. Este problema é um caso especial do problema do isomorfismo de subgrafos , que é conhecido por ser NP-completo. É também conhecido como um caso especial do problema do subgrupo oculto não abeliano sobre o grupo simétrico. (pt)
|
| rdfs:comment
|
- Unsolved problem in computer science: Can the graph isomorphism problem be solved in polynomial time? (more unsolved problems in computer science) The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. This problem is a special case of the subgraph isomorphism problem, which asks whether a given graph G contains a subgraph that is isomorphic to another given graph H; this problem is known to be NP-complete. It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group. (en)
- 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)
- En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. En pratique, l'isomorphisme de graphes est utilisé en chimie pour classer les molécules. (fr)
- O problema de isomorfismo de grafos é um problema computacional para determinar se dois grafos finitos são isomórficos. Não é conhecido se o problema pode ser solucionável em tempo polinomial nem se é NP-completo e, portanto, pode estar na classe de complexidade computacional NP-Intermediário. Sabe-se que o problema do isomorfismo do grafo está na baixa hierarquia da classe NP, o que implica que não é NP-completo a menos que a hierarquia de tempo polinomial colapse para o segundo nível.Ao mesmo tempo, o isomorfismo para muitas classes especiais de grafos pode ser resolvido em tempo polinomial, e na prática o isomorfismo do grafo pode ser resolvido de forma eficiente. (pt)
|
