We consider a wide series of classes of algorithmic complexity. We fix such a class and investigate the complexity of the inversion operation in classical algebraic structures, like groups or fields. In addition, we analyze the properties of quotient structures.
A.V.Aho, J.E.Hopcroft and J.D.Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.
2.
P.Alaev, Quotient structures and groups computable in polynomial time, Lecture Notes in Computer Science13296 (2022), 35–45. doi:10.1007/978-3-031-09574-0_3.
3.
P.E.Alaev, The complexity of inversion in groups, Algebra and Logic (2023), accepted for publication.
4.
P.E.Alaev and V.L.Selivanov, Fields of algebraic numbers computable in polynomial time. II, Algebra and Logic60(6) (2021), 349–359. doi:10.1007/s10469-022-09661-3.
5.
P.E.Alaev and V.L.Selivanov, Searching for applicable versions of computable structures, Lecture Notes in Computer Science12813 (2021), 1–11. doi:10.1007/978-3-030-80049-9_1.
6.
D.Cenzer and J.Remmel, Polynomial time versus recursive models, Annals of Pure and Applied Logic54(1) (1991), 17–58. doi:10.1016/0168-0072(91)90008-A.
7.
I.Kalimullin, A.Melnikov and K.M.Ng, Algebraic structures computable without delay, Theoretical Computer Science674 (2017), 73–98. doi:10.1016/j.tcs.2017.01.029.
