Graph isomorphism is in SPP
Graph isomorphism is in SPP
复制标题
DOI：
10.1109/sfcs.2002.1181999
复制
发表时间：
2002-11
期刊：
影响因子：
--
通讯作者：
V. Arvind;Piyush P. Kurur
中科院分区：
文献类型：
--
作者：
V. Arvind;Piyush P. Kurur
我们证明了图同构是在复杂性类SPP中，因此它是在/spl oplus/P中（事实上，对于每个k/spl ges/2，它是在Mod/sub k/P中）。我们得出这个结果作为一个推论的一个更一般的结果：我们表明，一个通用的问题，发现组有一个FP SPP算法。这个一般结果还有其他的结果：例如，在量子算法的背景下研究的置换群的隐子群问题，有一个FP/sup SPP/算法。此外，已知置换群上的一些其他算法问题至少与图同构（例如陪集相交）一样困难，这些问题在SPP中，因此在Mod/sub k/P中，对于每个k>2。
We show that graph isomorphism is in the complexity class SPP and hence it is in /spl oplus/P (in fact, it is in Mod/sub k/P for each k/spl ges/2). We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FP SPP algorithm. This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FP/sup SPP/ algorithm. Also, some other algorithmic problems over permutation groups known to be at least as hard as graph isomorphism (e.g. coset intersection) are in SPP, and thus in Mod/sub k/P for each k>2.