主題
Search

圖同構完備

對於圖同構測試，目前還沒有已知的 P 演算法，儘管該問題也未被證明是 NP 完全 的。事實上，如果 P 和 NP 完全之間存在裂縫（Skiena 1990，第 181 頁），那麼識別同構圖的問題似乎就落在這個裂縫中。因此，這個問題有時被歸類為一個特殊的圖同構完備複雜度類。

另請參閱

複雜度理論, 圖同構, 同構圖, NP 完全問題, P 問題

使用 探索

參考文獻

Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-156, 1983.Skiena, S. "Graph Isomorphism." §5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 181-187, 1990.

在 上被引用

圖同構完備

引用為

Weisstein, Eric W. "Graph Isomorphism Complete." From --A Resource. https://mathworld.tw/GraphIsomorphismComplete.html

主題分類