Graph isomorphism problem

Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC 246882287 Jacobo Torán, "On the hardness of graph isomorphism"

图同构（英語：graph isomorphism）描述的是图论中，两个图之间的完全等价关系。在图论的观点下，两个同构的图被当作同一个图来研究。 只有节点数目相同(即同阶)的两个图才有可能同构。两个简单图 G {\displaystyle G} 和 H {\displaystyle H} 称为是同构的，当且仅当存在一个将

速度最快的矩阵乘法算法是什么？ 可以在多项式时间内做整数分解吗？ 可以在多项式时间内计算离散对数吗？ 可以在多项式时间内解决图同构问题（英语：graph isomorphism problem）吗？ 可以在多项式时间内解决奇偶校验游戏（英语：parity game）吗？ 线性规划问题是否存在强多项式时间的解法？这是

對於長度為任意自然數n的字串，其最小超排列的長度。 艾狄胥-賈法斯猜想（英语：Erdős–Gyárfás conjecture） 图的同构问题（英语：Graph isomorphism problem） 关于单位距离的图的色数的Hadwiger-Nelson问题 为逾渗阈值（英语：percolation threshold）得到一种闭式表达式，特别是

{\displaystyle 2^{{\tilde {O}}(n^{1/3})}} ，其中輸入的長度為 n。另一個例子是圖形同構問題（英语：Graph isomorphism problem）的最著名演算法，其運算時間為 2 O ( n log ⁡ n ) {\displaystyle 2^{O({\sqrt {n\log