Communications of the ACM
Algorithmic Advance: The Group Isomorphism Problem
Credit: Baivector
A paper posted online in March 2023 has presented the first substantial progress in a half-century on one of the fundamental questions in the overlap between mathematics and computer science: how to recognize when two "groups"—basic algebraic structures—are really the same group in disguise.
Groups, which have been studied by mathematicians since the late 18th century, are among the most ubiquitous structures in mathematics. A group is a set of elements together with an operation (such as addition, multiplication, or composition) that turns two elements into a new one. To qualify as a group, the set must contain an "identity" element (one that leaves every element unchanged when combined with it by the operation); every element must have an inverse; and the operation (usually written *) must be associative, meaning that (a*b)*c always equals a*(b*c). There are, for example, groups of numbers or matrices or permutations, groups of symmetries of some object, and groups that measure the topological features of a shape.
No entries found