If someone asks you to determine whether two objects are the same, it might seem like a trivial request. In most everyday cases, a quick glance is enough for you to render an accurate judgment.
But in computer science, it’s a far more involved question. In fact, it’s one that cuts to the unresolved heart of what computers are capable of. Depending on what the objects are, and how you define sameness, we still don’t know whether computers can answer the question quickly, or whether a slow and laborious approach is essentially the best they can manage.
Over the last decade, there have been some important results demonstrating that computers can do at least a little better than that. One of the biggest recent results in computer science was a faster algorithm for determining when two graphs are the same. The 2015 work, by László Babai of the University of Chicago, broke one important computational speed barrier but fell short of another.
Now, a paper by Xiaorui Sun of the University of Illinois, Chicago has presented a new, faster algorithm for a related question called the group isomorphism problem, which is about knowing when two mathematical objects called groups are the same. The work, posted online this past March, takes a small step toward clarifying the underlying computational complexity involved in comparing objects.
Sun’s work breaks a long-standing speed limit for a particular class of groups — the one regarded as the hardest instance of the group isomorphism problem to solve. If an algorithm can quickly compare groups of this sort, the hope is that it can quickly compare groups of any type.
To read more, click here.