Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Graph_isomorphism_problem> ?p ?o }
- Graph_isomorphism_problem type Algorithm.
- Graph_isomorphism_problem type Article.
- Graph_isomorphism_problem type Function.
- Graph_isomorphism_problem type List.
- Graph_isomorphism_problem type Morphism.
- Graph_isomorphism_problem comment "The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete: it is one of only 12 such problems listed by Garey & Johnson (1979), and the only one of that list whose complexity remains unresolved.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 is known to be NP-complete. ".
- Graph_isomorphism_problem label "Graph isomorphism problem".
- Graph_isomorphism_problem sameAs Isomorfismiprobleem.
- Graph_isomorphism_problem sameAs Problxc3xa8me_de_lisomorphisme_de_graphes.
- Graph_isomorphism_problem sameAs m.068cxm.
- Graph_isomorphism_problem sameAs Problem_izomorfizma_grafova.
- Graph_isomorphism_problem sameAs Q3738036.
- Graph_isomorphism_problem sameAs Q3738036.
- Graph_isomorphism_problem wasDerivedFrom Graph_isomorphism_problem?oldid=682701928.
- Graph_isomorphism_problem isPrimaryTopicOf Graph_isomorphism_problem.