文章基本信息

标题：Graph Isomorphism is not AC^0 reducible to Group Isomorphism
本地全文：下载
作者：Arkadev Chattopadhyay ; Jacobo Toran ; Fabian Wagner 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with O(loglogn) depth and O(log2n) nondeterministic bits, where n is the number of group elements. This improves the existing upper bound from Wolf for the problems. In the previous upper bound the circuits have bounded fan-in but depth O(log2n) and also O(log2n) nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC0 reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or Quasigroup Isomorphism under the ordering defined by AC0 reductions.
关键词：Isomorphism problems