RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2023 Volume 62, Number 2, Pages 155–178 (Mi al2755)

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.

UDC: 510.52+510.67+512.54

Received: 12.05.2022
Revised: 31.01.2024

DOI: 10.33048/alglog.2023.62.201



© Steklov Math. Inst. of RAS, 2025