Comparing Comparisons - Does isomorphism hold the key to a computer's ability to test sameness?

Sunday - June 25 2023, 13:58 UTC - 1 year ago

Two objects can be considered the same through isomorphism, where they contain the same elements and the same relationships with each other. Computer science has seen advancements over the past decade on algorithms for graph and group isomorphism which provide interesting implications for computer hardware and software design.

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.

"We don’t know such a theorem, but we have reason to believe something like that should be true," said Josh Grochow of the University Colorado, Boulder.

Comparing Comparisons .

To determine whether two things are the same in a precise way, you first need to define "the same." Two strings of numbers could be considered the same if they merely contain the same digits, or they might need to have the same digits in the same order.

Isomorphism is a particular kind of sameness that comes up a lot in mathematics. When two objects are isomorphic to each other, it roughly means that they contain the same elements, and that those elements are in the same relationship with each other.

Graphs — collections of vertices (dots) linked by edges (lines) — provide an accessible, visual way to see what isomorphism can look like. Two graphs are isomorphic if you can match vertices in one graph with vertices in the other, such that vertices that are connected by an edge in the first graph are connected by an edge in the second. Isomorphic graphs can look different on the surface, but they share an underlying structure.

Groups are more abstract than graphs, but they’re still amenable to comparison by isomorphism. A group is a collection of elements — such as numbers — that can be combined with each other according to some operation so that the result is also in the collection. For example, you can have a group whose elements are the integers — all the positive and negative whole numbers, plus zero — and whose operation is addition: Ad .