abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The te ...

, the group isomorphism problem is the

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

of determining whether two given finite group presentations refer to isomorphic groups. The isomorphism problem was formulated by

Max Dehn Max Wilhelm Dehn (November 13, 1878 – June 27, 1952) was a German mathematician most famous for his work in geometry, topology and geometric group theory. Born to a Jewish family in Germany, Dehn's early life and career took place in Germany. H ...

, and together with the word problem and conjugacy problem, is one of three fundamental decision problems in group theory he identified in 1911. All three problems are undecidable: there does not exist a computer algorithm that correctly solves every instance of the isomorphism problem, or of the other two problems, regardless of how much time is allowed for the algorithm to run. In fact the problem of deciding whether a group is trivial is undecidable, (See Corollary 3.4) a consequence of the Adian–Rabin theorem due to Sergei Adian and

Michael O. Rabin Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician and computer scientist and a recipient of the Turing Award. Biography Early life and education Rabin was born in 1931 in ...

References

* Group theory Undecidable problems {{Abstract-algebra-stub