In this paper, we show that Graph Isomorphism (GI) is not $\textsf{AC}^{0}$-reducible to several problems, including the Latin Square Isotopy problem, isomorphism testing of several families of Steiner designs, and isomorphism testing of conference graphs. As a corollary, we obtain that GI is not $\textsf{AC}^{0}$-reducible to isomorphism testing of Latin square graphs and strongly regular graphs arising from special cases of Steiner $2$-designs. We accomplish this by showing that the generator-enumeration technique for each of these problems can be implemented in $\beta_{2}\textsf{FOLL}$, which cannot compute Parity (Chattopadhyay, Tor\'an, & Wagner, ACM Trans. Comp. Theory, 2013).
翻译：在本文中，我们展示了图同构问题（GI）无法被$\textsf{AC}^{0}$归约到多个问题中，包括拉丁方同构问题、数个Steiner设计族的同构测试问题以及会议图的同构测试问题。作为一个推论，我们得到了GI无法被$\textsf{AC}^{0}$归约到拉丁方图同构测试和强正则图同构测试问题下特殊情况下的Steiner $2$-设计图同构测试中。我们通过展示每个问题的生成器枚举技术可以在$\beta_{2}\textsf{FOLL}$中实现，从而完成这一点。而$\beta_{2}\textsf{FOLL}$是无法计算Parity（Chattopadhyay、Tor\'an和Wagner，ACM Trans. Comp. Theory, 2013）的。
相关内容
微信扫码咨询专知VIP会员