• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Algorithms for Group Isomorphism via Group Extensions and Cohomology
【24h】

Algorithms for Group Isomorphism via Group Extensions and Cohomology

机译：通过组扩展和协调的组同构族算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The isomorphism problem for groups given by their multiplication tables (GPI) has long been known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. Thus, at present it is crucial to understand groups with abelian normal subgroups to develop n^o(log n)-time algorithms. Towards this goal we advocate a strategy via the extension theory of groups, which describes how a normal subgroup N is related to G/N via G. This strategy "splits" GPI into two sub problems: one regarding group actions on other groups, and one regarding group co homology. The solution of these problems is essentially necessary and sufficient to solve GPI. Most previous works naturally align with this strategy, and it thus helps explain in a unified way the recent polynomial-time algorithms for other group classes. In particular, most prior results in the multiplication table model focus on the group action aspect, despite the general necessity of co homology, for example for p-groups of class 2-believed to be the hardest case of GPI. To make progress on the group co homology aspect of GPI, we consider central-radical groups, proposed in Babai et al. (SODA 2011): the class of groups such that G mod its center has no abelian normal subgroups. Recall that Babai et al. (ICALP 2012) consider the class of groups G such that G itself has no abelian normal subgroups. Following the above strategy, we solve GPI in n^O(log log n) time for central-radical groups, and in polynomial time for several prominent subclasses of central-radical groups. We also solve GPI in n^O(log log n)-time for groups whose solvable normal subgroups are elementary abelian but not necessarily central. As far as we are aware, this is the first time that a nontrivial algorithm with worst-case guarantees has tackled both aspects of GPI-actions a- d cohomology-simultaneously. Prior to this work, only n^O(log n)-time algorithms were known, even for groups with a central radical of constant size, such as Z(G) = Z_2. To develop these algorithms we utilize several mathematical results on the detailed structure of cohomology classes, as well as algorithmic results for code equivalence, coset intersection and cyclicity testing of modules over finite-dimensional associative algebras. We also suggest several promising directions for future work.
机译：通过他们的乘法表（GPI）给出组的同构问题一直被称为是在正^ O（log n）的时间内可解，但直到最近才出现了对多项式时间显著的进展。例如，鲍鲍伊等。 （ICALP 2012），得到为基的多项式时间算法，没有正常阿贝尔群。因此，目前是至关重要的理解与阿贝尔正常子组团体制定N R个为O（log n）的-time算法。为了实现这一目标，我们主张通过群体的扩展理论，描述了一个正常的子群N通过G.这一战略“分裂” GPI相关至G / N为两个子问题的策略：在其他团体一个关于集体行动，并一个关于集团有限公司的同源性。这些问题的解决方案基本上是必要且充分的解决GPI。大多数以前的作品自然与此战略相一致，因此有助于以统一的方式解释为另一组类近期多项式算法。在乘法表模型集中在组动作方面，特别地，大多数现有的结果，尽管共同的同源性一般必要性，例如用于类的p型基团2-认为是GPI最难情况。如果要对GPI的集团有限公司的同源性方面的进步，我们认为中央激进团体，在八佰伴等人提出。 （SODA 2011）：类基团的，使得G国防部其中心没有阿贝尔正常子组。回想一下，八佰伴等。 （ICALP 2012）考虑类组G1，使得G本身没有阿贝尔正常子组。按照上述策略，我们解决了GPI的N 2 O（log日志n）次中央激进团体，并在多项式时间内为中央激进组织的几个著名的子类。我们还解决了GPI的N 2 O（log日志N） - 时间的，其解决的正规子是基本阿贝尔但不一定中心组。据我们所知，这是第一次，一个平凡的算法最坏情况下保证了A-d的上同调，同时攻克了GPI-行动两个方面。在此之前的工作，n只有2 O（log n）的-time算法是已知的，即使对于具有中央自由基恒定大小的基团，如Z（G）= Z_2。为了发展这些算法，我们利用上同调类的详细结构的几个数学结果，以及用于代码等价，陪集相交并经有限维结合代数模块的周期性测试算法结果。我们还建议今后工作的几个有前途的方向。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号