Difference between revisions of "Isomorphism problem"
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
| Line 1: | Line 1: | ||
| − | + | <!-- | |
| + | i0528501.png | ||
| + | $#A+1 = 4 n = 0 | ||
| + | $#C+1 = 4 : ~/encyclopedia/old_files/data/I052/I.0502850 Isomorphism problem | ||
| + | Automatically converted into TeX, above some diagnostics. | ||
| + | Please remove this comment and the {{TEX|auto}} line below, | ||
| + | if TeX found to be correct. | ||
| + | --> | ||
| − | The isomorphism problem is unsolvable for many important classes of algebraic systems. The unsolvability of the partial isomorphism problem for a finitely-presented semi-group in the class of all finitely-presented semi-groups was established in [[#References|[2]]], and that for finitely-presented groups in the class of all finitely-presented groups in [[#References|[1]]]. The isomorphism problem for groups in the variety of solvable groups of solvability length | + | {{TEX|auto}} |
| + | {{TEX|done}} | ||
| + | |||
| + | The problem of describing an [[Algorithm|algorithm]] that enables one to establish whether or not any pair of recursively-presented algebraic systems (cf. [[Algebraic system|Algebraic system]]) in a given class are isomorphic. The partial isomorphism problem for a fixed algebraic system $ A $ | ||
| + | consists of describing an algorithm that recognizes whether or not a recursively-presented algebraic system in the class under discussion is isomorphic to $ A $. | ||
| + | A positive solution of the (partial) isomorphism problem consists of a description of the desired algorithm (the respective problem is solvable); a negative solution consists of proving that no algorithm exists (the respective problem is unsolvable). Usually, this isomorphism problem is formulated for algebras given by generators and defining relations. | ||
| + | |||
| + | The isomorphism problem is unsolvable for many important classes of algebraic systems. The unsolvability of the partial isomorphism problem for a finitely-presented semi-group in the class of all finitely-presented semi-groups was established in [[#References|[2]]], and that for finitely-presented groups in the class of all finitely-presented groups in [[#References|[1]]]. The isomorphism problem for groups in the variety of solvable groups of solvability length $ n $, | ||
| + | given in the variety by a finite number of generators and relations, is also unsolvable for $ n \geq 7 $[[#References|[3]]]. | ||
The isomorphism problem is solvable in the class of all finite finitely-presented algebras of fixed signature, and in the class of Abelian groups. | The isomorphism problem is solvable in the class of all finite finitely-presented algebras of fixed signature, and in the class of Abelian groups. | ||
Latest revision as of 22:13, 5 June 2020
The problem of describing an algorithm that enables one to establish whether or not any pair of recursively-presented algebraic systems (cf. Algebraic system) in a given class are isomorphic. The partial isomorphism problem for a fixed algebraic system $ A $
consists of describing an algorithm that recognizes whether or not a recursively-presented algebraic system in the class under discussion is isomorphic to $ A $.
A positive solution of the (partial) isomorphism problem consists of a description of the desired algorithm (the respective problem is solvable); a negative solution consists of proving that no algorithm exists (the respective problem is unsolvable). Usually, this isomorphism problem is formulated for algebras given by generators and defining relations.
The isomorphism problem is unsolvable for many important classes of algebraic systems. The unsolvability of the partial isomorphism problem for a finitely-presented semi-group in the class of all finitely-presented semi-groups was established in [2], and that for finitely-presented groups in the class of all finitely-presented groups in [1]. The isomorphism problem for groups in the variety of solvable groups of solvability length $ n $, given in the variety by a finite number of generators and relations, is also unsolvable for $ n \geq 7 $[3].
The isomorphism problem is solvable in the class of all finite finitely-presented algebras of fixed signature, and in the class of Abelian groups.
The isomorphism problem for nilpotent groups of class 2 and for groups with one defining relation is still open (1988). The isomorphism problem for groups is connected with algorithmic problems in topology.
References
| [1] | S.I. Adyan, "Unsolvability of some algorithmic problems in group theory" Trudy Moskov. Mat. Obshch. , 6 (1957) pp. 231–298 (In Russian) |
| [2] | A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954)) |
| [3] | A.S. Kirkinskii, V.N. Remeslennikov, "The isomorphism problem for solvable groups" Math. Notes , 18 : 3 (1975) pp. 849–853 Mat. Zametki , 18 : 3 (1975) pp. 437–443 |
Isomorphism problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Isomorphism_problem&oldid=17642