# Comparing two character tables

Suppose that you are given two finite groups, for example, via their Cayley tables.

One can efficiently compute their character tables (efficiently = polynomial time in the order of the group), this is a result of Babai and Rònyai from 1990.

It is well-known that the character table does not determine the group (e.g. $Q_8$ and $D_4$ are non-isomorphic groups with the same character table), nevertheless, I am interested in the following:

Question: Is there an efficient way to check whether two character tables are the same?

-
My memory, from conversations with people who compute character tables, is that this is regarded as a potentially difficult problem. –  Derek Holt Jun 23 '13 at 18:27
@DerekHolt, I suspect that that this is indeed the situation. Can you be more specific though, when is this problem hard? are there families for which there is a polynomial time algorithm to check this? –  DKal Jun 23 '13 at 19:40
I don't know of any specific results in this direction. It will clearly only be hard if there are large numbers of characters having the same degrees, or large numbers of conjugacy classes of the same size. –  Derek Holt Jun 24 '13 at 19:06
@DerekHolt, how do you deduce "... only be hard if..."? I understand that in case we have many conjugacy classes of the same size (AND which contain elements of the same order!), or in case we have many characters of the same degree, this problem should be hard. But why do you write only? –  DKal Jun 27 '13 at 10:58
@DerekHolt, one more thing, can you give a bound on the number of conjugacy classes (of elements of the same order) of the same size, and/or a bound on the number of characters of the same degree, such that comparing the character tables is polynomial time? –  DKal Jun 27 '13 at 11:03