Group isomorphism problem

Last updated

In abstract algebra, the group isomorphism problem is the decision problem of determining whether two given finite group presentations refer to isomorphic groups.

The isomorphism problem was formulated by Max Dehn, [1] and together with the word problem and conjugacy problem, is one of three fundamental decision problems in group theory he identified in 1911. [2] 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, [3] a consequence of the Adian–Rabin theorem due to Sergei Adian and Michael O. Rabin.

The group isomorphism problem, in which the groups are given by multiplication tables, can be reduced to a graph isomorphism problem but not vice versa. [4] Both have quasi-polynomial-time algorithms, the former since 1978 attributed to Robert Tarjan [5] and the latter since 2015 by László Babai. [6] A small but important improvement for the case p-groups of class 2 was obtained in 2023 by Xiaorui Sun. [7] [4]

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group is the algorithmic problem of deciding whether two words in the generators represent the same element. More precisely, if is a finite set of generators for then the word problem is the membership problem for the formal language of all words in and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on to the group . If is another finite generating set for , then the word problem over the generating set is equivalent to the word problem over the generating set . Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group .

<span class="mw-page-title-main">Interactive proof system</span>

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

<span class="mw-page-title-main">Graph isomorphism</span> Bijection between the vertex set of two graphs

In graph theory, an isomorphism of graphsG and H is a bijection between the vertex sets of G and H

<span class="mw-page-title-main">Max Dehn</span> German-American mathematician (1878–1952)

Max Wilhelm Dehn was a German mathematician most famous for his work in geometry, topology and geometric group theory. Dehn's early life and career took place in Germany. However, he was forced to retire in 1935 and eventually fled Germany in 1939 and emigrated to the United States.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

<span class="mw-page-title-main">László Babai</span> Hungarian mathematician and computer scientist

László "Laci" Babai is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields.

In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. A deep result of computational theory is that answering this question is in many important cases undecidable.

In abstract algebra, the conjugacy problem for a group G with a given presentation is the decision problem of determining, given two words x and y in G, whether or not they represent conjugate elements of G. That is, the problem is to determine whether there exists an element z of G such that

In mathematics, a Hopfian group is a group G for which every epimorphism

In the mathematical subject of group theory, the rank of a groupG, denoted rank(G), can refer to the smallest cardinality of a generating set for G, that is

In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have "small overlaps" with each other. Small cancellation conditions imply algebraic, geometric and algorithmic properties of the group. Finitely presented groups satisfying sufficiently strong small cancellation conditions are word hyperbolic and have word problem solvable by Dehn's algorithm. Small cancellation methods are also used for constructing Tarski monsters, and for solutions of Burnside's problem.

In graph theory, a branch of mathematics, graph canonization is the problem of finding a canonical form of a given graph G. A canonical form is a labeled graph Canon(G) that is isomorphic to G, such that every graph that is isomorphic to G has the same canonical form as G. Thus, from a solution to the graph canonization problem, one could also solve the problem of graph isomorphism: to test whether two graphs G and H are isomorphic, compute their canonical forms Canon(G) and Canon(H), and test whether these two canonical forms are identical.

Eugene Michael Luks is an American mathematician and computer scientist, a professor emeritus of computer and information science at the University of Oregon. He is known for his research on the graph isomorphism problem and on algorithms for computational group theory.

Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.

In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.

In the mathematical subject of group theory, the Adian–Rabin theorem is a result that states that most "reasonable" properties of finitely presentable groups are algorithmically undecidable. The theorem is due to Sergei Adian (1955) and, independently, Michael O. Rabin (1958).

References

  1. ↑ Dehn, Max (1911). "Über unendliche diskontinuierliche Gruppenn". Math. Ann. 71: 116–144. doi:10.1007/BF01456932. S2CID   123478582.
  2. ↑ Magnus, Wilhelm; Karrass, Abraham & Solitar, Donald (1996). Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations (2nd ed.). New York: Dover Publications. pp. 24–29. ISBN   0486632814 . Retrieved 14 October 2022– via VDOC.PUB.
  3. ↑ Miller, Charles F. III (1992). "Decision Problems for Groups—survey and Reflections" (PDF). In Baumslag, Gilbert; Miller, C. F. III (eds.). Algorithms and Classification in Combinatorial Group Theory . Mathematical Sciences Research Institute Publications. Vol. 23. New York: Springer-Verlag. pp. 1–59. doi:10.1007/978-1-4613-9730-4_1. ISBN   9781461397328. (See Corollary 3.4)
  4. 1 2 Hartnett, Kevin (23 June 2023). "Computer Scientists Inch Closer to Major Algorithmic Goal". Quanta Magazine .
  5. ↑ Miller, Gary L. (1978). "On the nlog n isomorphism technique (A Preliminary Report)". Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78. ACM Press. pp. 51–58. doi:10.1145/800133.804331. ISBN   978-1-4503-7437-8.
  6. ↑ Babai, László (January 9, 2017), Graph isomorphism update
  7. ↑ Sun, Xiaorui (2023). "Faster Isomorphism for p-Groups of Class 2 and Exponent p". arXiv: 2303.15412 [cs.DS].


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.