Abstract: We prove that every quotient structure of the form ${\mathscr A}/E$, where ${\mathscr A}$ is a structure computable in polynomial time ($\text {\rm P}$-computable), and $E$ is a $\text {\rm P}$-computable congruence in ${\mathscr A}$, is isomorphic to a $\text {\rm P}$-computable structure. We also prove that for every $\text {\rm P}$-computable group ${\mathscr A} = (A,\cdot) $, there is a $\text {\rm P}$-computable group $ {\mathscr B}\cong{\mathscr A} $, in which the inversion operation $x^{-1}$ is also $\text {\rm P}$-computable.

Cite: Alaev P.
Quotient structures and groups computable in polynomial time
17th International Computer Science Symposium in Russia 29 Jun - 1 Jul 2022