An Annoying Problem
It’s the stupid questions that have some of the most surprising and interesting answers — Cory Doctorow
|
| ACM Turing Award source |
Robert Tarjan is well known to most—a Turing award winner in 1986 with John Hopcroft. Bob is a professor of Computer Science at Princeton University, and one of the world experts on linear time graph algorithms. I always thought if some NP-complete graph problem had a linear time algorithm, then P=NP would have long been solved by Bob.
Today we talk about a problem that hasn’t been solved by Bob.
The problem I mean was quasi-solved by Bob. That is, he gave a quasi-polynomial time algorithm. The problem is group isomorphism (GpI). Laci Babai discusses its relation as a special case of graph isomorphism (GI) in section 13.2 of his famous 2016 paper giving a quasi-polynomial time algorithm for GI. He says that the annoyance of GpI should temper expectations for getting GI into polynomial time, because:
[I]n spite of considerable effort and the availability of powerful algebraic machinery, Group Isomorphism is still not known to be in
.
Bob’s Least Result
Bob has many great and deep results. For example, Donald Knuth described Bob’s strong connected component algorithm for directed graphs in these words:
The data structures that he devised for this problem fit together in an amazingly beautiful way, so that the quantities you need to look at while exploring a directed graph are always magically at your fingertips.
Here is Ken’s slight editing of Wikipedia’s presentation:
Input: Graph G = (V,E) whose nodes have fields int index, int lowlink, bool onStack
Output: The set of subsets of V denoting the strongly connected components
Stack S := empty stack;
int index := 0; //global variable with invariant: index = smallest unused index
proc strongconnect(v):
v.index := index; v.lowlink := index; index++;
S.push(v); v.onStack := true;
for each w such that (v,w) is in E:
if w.index is undefined then: //w not yet visited so recurse on it
strongconnect(w);
v.lowlink = min{v.lowlink,w.lowlink} //lowest-indexed node reached
else if w.onStack then:
v.lowlink = min(v.lowlink, w.index);
//clever: w.index was lowest unused index at the time
else:
pass; //(v,w) goes to already-found component, so ignore.
end if;
end for
if v.lowlink == v.index then: //we've completed a component so pop and output it
repeat:
Node w = S.pop();
w.onStack = false;
output w as part of the current strongly connected component;
until w == v;
end if;
end proc;
for each v in V do:
if v.index is undefined then:
strongconnect(v);
end if;
end for;
The Annoying Problem
Just over ten years ago we talked about: How do we tell if two groups are isomorphic? Precisely on October 8, 2011 we talked about group isomorphism. We called it an annoying problem. It remains annoying.
In the group isomorphism problem (GpI), we are given two finite groups 
Bob Tarjan famously noted that this could be done 
Theorem 1 General group isomorphism is in
deterministic time where
is the smallest prime dividing the order of the group.
Better than Bob’s insight, but still not polynomial time.
Order Restriction
The results to date on GpI have relied mainly on basic group theory. Bob’s result uses an elementary fact about finite groups. David uses the same insight and adds a deep fact about isomorphism type problems. Neither use any of the “millions” of theorems known about finite groups.
I wondered if there is some hope to start to exploit more of the papers on group structure? The trouble I think is that these results are quite difficult for those not in group theory to understand. But perhaps there is some hope. What do you think?
I still wonder if there is a polynomial time algorithm for the general group isomorphism problem? Can we eliminate the 
Theorem 2 Let
and
be finite groups of order
that is square free.Then
can be determined in time polynomial in
That is, 
But Wait…
As I worked on this I found a nice paper by Heiko Dietrich and James Wilson, titled “Polynomial Time Isomorphism Tests Of Black-Box Type Groups Of Most Orders.” They reference another paper that proved a stronger theorem than our above one:
Theorem 3 There is an algorithm that given groups
. The algorithm runs in time polynomial in the input size.
Proof of Our Theorem
Definition 4 A finite group
so that
are both cyclic.
Every finite group of square-free order (i.e. the order is not divisible by the square of a natural number) is metacyclic.
Proof: We claim that
Their stronger proof uses quite a bit more group theory. But our simple proof may give you some intuition why the restriction on the order of the group helps.
Open Problems
The above result fits well with the belief that the worst case for isomorphism is when the order of the groups is a power of a prime. Some possible conjectures are:
-
Can we generalize “
does not divide
does not divide
-
Let
and
. Then GpI is in polynomial time.
Definition 5 A finite group
- What if we replace metacyclic by metabelian?
I suppose you meant ” … we are given two finite groups {G} and {H} of degree (not order) {n}”.
Thx for the instructive article Prof. Lipton. I might pass a long a somewhat easier and better claim Heiko and I proved this year and which will appear in FOCS proceedings 2022 ( arXiv:2011.03133). We prove:
Along with that we show you can prove a Cayley table is the multiplication of a group in nearly linear time. To proof use a mix of group theory, number theory, and some special data structures studied by Sims, Babai, Luks, and Knuth. We hope it will inspire more progress on this indeed “Annoying Problem”. For interested readers the introduction and bibliography give an account of the many recent efforts on this problem.
Why is this problem important?
It is a major special case of the Graph Isomorphism problem, and like it is one of the few remaining natural problems that currently has “NP-Intermediate” status between being (known to be) in P versus NP-complete. The relation between GpI and GI speaks to how much combinatorics of the latter is captured by group theory.
Why is this problem important to CS theory if this problem is in P? I think you are addressing the importance of CS theory to this problem so that it can be placed in P.
Choosing an “NP-intermediate” in that manner may advance CS in an important way?
If P is NP, the capture is 100%. Otherwise, any significance?
Personal answer: Graph Isomorphism is the base case of comparing data, Groups are the inductive step.
To expand, programs use ‘equals’ but that only compares things precisely, as bits in memory. But data is often more nuanced “equivalent up to …” and you get a tower of ever finer equivalences ending in the precise machine level bits in memory. Formally that is known as an n-groupoid (n-levels). I.e. transitive law-> group multiplication, symmetric law->inverses, reflexive law->identity. The finite isomorphism problem on the base case n=0 is essentially reducible to GI, folks say “GI is universal for structure”. For n>0 the problem becomes GpI.
Real question: maybe equality always requires some up front harder problem like GI, but after that GpI takes over and is perhaps much easier. Presently though both are equally hard.
Back down to earth: my goal (and that of many others) is to see us make better tools for equality so we might for example decrease the amounts of wasted storage on duplicates and see past differences in the process of data collection and see the actual information. GI and GpI get at the heart of the hard problems in this effort.
I understand all this but what use is this problem or GI being in P is to CS theory assuming P is NP?
@Testing: Yes if NP==P, then it all amounts to nothing– nothing more than a polynomial transformation.
BTW, there are many many “stupid questions”, that remain stupid. Yet another one is enumeration of the perfect matching in a complete bipartite graph.