|
The complexity of inversion in groups
P. E. Alaev Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
Abstract:
We prove that if ${\mathscr A}=(A,\cdot)$ is a group computable in polynomial time (${\rm P}$-computable), then there exists a ${\rm P}$-computable group ${\mathscr B}=(B,\cdot)\cong{\mathscr A}$, in which the operation $x^{-1}$ is also ${\rm P}$-computable. On the other hand, we show that if the center $Z({\mathscr A})$ of a group ${\mathscr A}$ contains an element of infinite order, then under some additional assumptions, there exists a ${\rm P}$-computable group ${\mathscr B}'=(B',\cdot)\cong{\mathscr A}$, in which the operation $x^{-1}$ is not primitive recursive. Also the following general fact in the theory of ${\rm P}$-computable structures is stated: if ${\mathscr A}$ is a ${\rm P}$-computable structure and $E\subseteq A^{2}$ is a ${\rm P}$-computable congruence on ${\mathscr A}$, then the quotient structure ${\mathscr A} / E$ is isomorphic to a ${\rm P}$-computable structure.
Keywords:
computable group, inversion operations, primitive recursive function, quotient structure.
Received: 12.05.2022 Revised: 31.01.2024
Citation:
P. E. Alaev, “The complexity of inversion in groups”, Algebra Logika, 62:2 (2023), 155–178
Linking options:
https://www.mathnet.ru/eng/al2755 https://www.mathnet.ru/eng/al/v62/i2/p155
|
Statistics & downloads: |
Abstract page: | 68 | Full-text PDF : | 34 | References: | 21 |
|