文章基本信息

标题：Graph Isomorphism is in SPP
本地全文：下载
作者：V. Arvind, Piyush P Kurur
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that Graph Isomorphism is in the complexity class SPP, and hence it is in \ParityP (in fact, it is in \ModkP for each k 2 ). We derive this result as a corollary of a more general result: we show that a {\em generic problem} \FINDGROUP has an \FP \SPP algorithm. This general result has other consequences: for example, it follows that the {\em hidden subgroup problem} for permutation groups, studied in the context of quantum algorithms, has an \FP \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 \ModkP for k 2 .
关键词：gap-definable complexity classes , Graph Isomorphism , lowness.