Testing isomorphism of combinatorial and algebraic structures.

摘要

Our main results are algorithms to test isomorphism of hypergraphs and of groups.;We give an algorithm to test isomorphism of hypergraphs of rank k in time exp(O(k² n )), where n is the number of vertices (joint work with L. Babai, FOCS 2008). (The rank is the maximum size of hyperedges; the tilde refers to a polylogarithmic factor.) The case of bounded k answered a then 24-year-old question and removes an obstacle to improving the worst-case bound for Graph Isomorphism testing. The best previously known bound, even for k = 3, was Cn (Luks 1999).;We consider the problem of testing isomorphism of groups of order n given by Cayley tables. The nlog n bound on the time complexity for the general case has not been improved over the past four decades. We demonstrate that the obstacle to efficient algorithms is the presence of abelian normal subgroups; we show this by giving a polynomial-time isomorphism test for "semisimple groups," defined as groups without abelian normal subgroups (joint work L. Babai, Y. Qiao, in preparation). This concludes a project started with L. Babai, J. A. Grochow, Y. Qiao (SODA 2011). That paper gave an n log log n algorithm for this class, and gave polynomial-time algorithms assuming boundedness of certain parameters. The key ingredients for this algorithm are: (a) an algorithm to test permutational isomorphism of permutation groups in time polynomial in the order and simply exponential in the degree; (b) the introduction of the "twisted code equivalence problem," a generalization of the classical code equivalence problem by admitting a group action on the alphabet; (c) an algorithm to test twisted code equivalence; (d) a reduction of semisimple group isomorphism to permutational isomorphism of transitive permutation groups under the given time limits via "twisted code equivalence.";The twisted code equivalence problem and the problem of permutational isomorphism of permutation groups are of interest in their own right.