Geodesic
The complexity of inversion in groups
Algebra i logika, Tome 62 (2023) no. 2, pp. 155-178.

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Mots-clés : quotient structure. 
@article{AL_2023_62_2_a0,
     author = {P. E. Alaev},
     title = {The complexity of inversion in groups},
     journal = {Algebra i logika},
     pages = {155--178},
     publisher = {mathdoc},
     volume = {62},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2023_62_2_a0/}
}
TY  - JOUR
AU  - P. E. Alaev
TI  - The complexity of inversion in groups
JO  - Algebra i logika
PY  - 2023
SP  - 155
EP  - 178
VL  - 62
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2023_62_2_a0/
LA  - ru
ID  - AL_2023_62_2_a0
ER  - 
%0 Journal Article
%A P. E. Alaev
%T The complexity of inversion in groups
%J Algebra i logika
%D 2023
%P 155-178
%V 62
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2023_62_2_a0/
%G ru
%F AL_2023_62_2_a0
P. E. Alaev. The complexity of inversion in groups. Algebra i logika, Tome 62 (2023) no. 2, pp. 155-178. http://geodesic.mathdoc.fr/item/AL_2023_62_2_a0/

[1] D. Cenzer, J. Remmel, “Polynomial-time versus recursive models”, Ann. Pure Appl. Logic, 54:1 (1991), 17–58 | DOI | MR | Zbl

[2] D. Cenzer, J. Remmel, “Polynomial-time Abelian groups”, Ann. Pure Appl. Logic, 56:1–3 (1992), 313–363 | DOI | MR | Zbl

[3] P. E. Alaev, “Struktury, vychislimye za polinomialnoe vremya. I”, Algebra i logika, 55:6 (2016), 647–669 | MR

[4] P. E. Alaev, “Polinomialno vychislimye struktury s konechnym chislom porozhdayuschikh”, Algebra i logika, 59:3 (2020), 385–394 | MR | Zbl

[5] P. E. Alaev, “Konechno porozhdennye struktury, vychislimye za polinomialnoe vremya”, Sib. matem. zh., 63:5 (2022), 953–974

[6] P. E. Alaev, V. L. Selivanov, “Polya algebraicheskikh chisel, vychislimye za polinomialnoe vremya. I”, Algebra i logika, 58:6 (2019), 673–705 | MR

[7] D. Cenzer, J. B. Remmel, “Complexity theoretic model theory and algebra”, Handbook of recursive mathematics, v. 1, Stud. Logic Found. Math., 138, Recursive model theory, eds. Yu. L. Ershov et al., Elsevier, Amsterdam, 1998, 381–513 | DOI | MR | Zbl

[8] N. Bazhenov, M. Harrison-Trainor, I. Kalimullin, A. Melnikov, K. M. Ng, “Automatic and polynomial-time algebraic structures”, J. Symb. Log., 84:4 (2019), 1630–1669 | DOI | MR | Zbl

[9] P. E. Alaev, V. L. Selivanov, “Polya algebraicheskikh chisel, vychislimye za polinomialnoe vremya. II”, Algebra i logika, 60:6 (2021), 533–548 | MR

[10] P. E. Alaev, V. L. Selivanov, “Searching for applicable versions of computable structures”, Connecting with computability, 17th conf. on computability in Europe, CiE 2021, Proc. (virtual event, Ghent, Belgium, July 5–9, 2021), Lect. Notes Comput. Sci., 12813, eds. L. De Mol et al., Springer, Cham, 2021, 1–11 | DOI | MR

[11] A. V. Aho, J. E. Hopcroft, J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Ser. Comput. Sci. Inform. Process., Addison-Wesley Publ. Co, Reading, Mass. etc., 1974 | MR | Zbl

[12] I. Kalimullin, A. Melnikov, K. M. Ng, “Algebraic structures computable without delay”, Theoret. Comput. Sci., 674 (2017), 73–98 | DOI | MR | Zbl