论文标题
关于识别强烈规则图的复杂性
On the Complexity of Identifying Strongly Regular Graphs
论文作者
论文摘要
在本文中，我们表明图形同构（GI）不是$ \ textsf {ac}^{0} $ - 可降低到几个问题，包括拉丁方形同位素问题，同构测试Steiner设计家族的同构测试，以及会议图的同构态测试。作为推论，我们获得GI不是$ \ textsf {ac}^{0} $ - 可还原为拉丁方形图的同构测试，并且是由Steiner $ 2 $ -Designs引起的强烈常规图。我们通过证明可以在$β_{2} \ textsf {foll} $中实现的每种问题的生成器 - 数字技术来实现这一目标，该技术无法计算奇偶校验（Chattopadhyay，Torán，＆Wagner，ACMTrans。Comp。Prodem，2013年）。
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 $β_{2}\textsf{FOLL}$, which cannot compute Parity (Chattopadhyay, Torán, & Wagner, ACM Trans. Comp. Theory, 2013).
