Complexity of the inversion operation in groups Full article
| Journal |
Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302 |
||
|---|---|---|---|
| Output data | Year: 2023, Volume: 62, Number: 2, Pages: 103-118 Pages count : 16 DOI: 10.1007/s10469-024-09730-9 | ||
| Tags | computable group, inversion operations, primitive recursive function, quotient structure | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0011 |
Abstract:
We prove that if A =(A,·) is a group computable in polynomial time (P-computable), then there exists a P-computable group B =(B,·) ∼ =A, in which the operation x−1 is also P-computable. On the other hand, we show that if the center Z(A ) of a group A contains an element of infinite order, then under some additional assumptions, there exists a P-computable group B=(B,·) ∼ = A, in which the operation x−1 is not primitive recursive. Also the following general fact in the theory of P-computable structures is stated: if A is a P-computable structure and E ⊆ A2 is a P-computable congruence on A , then the quotient structure A /E is isomorphic to a P-computable structure.
Cite:
Alaev P.E.
Complexity of the inversion operation in groups
Algebra and Logic. 2023. V.62. N2. P.103-118. DOI: 10.1007/s10469-024-09730-9 WOS Scopus РИНЦ OpenAlex
Complexity of the inversion operation in groups
Algebra and Logic. 2023. V.62. N2. P.103-118. DOI: 10.1007/s10469-024-09730-9 WOS Scopus РИНЦ OpenAlex
Original:
Алаев П.Е.
Сложность операции обращения в группах
Алгебра и логика. 2023. Т.62. №2. С.155-178. DOI: 10.33048/alglog.2023.62.201 РИНЦ
Сложность операции обращения в группах
Алгебра и логика. 2023. Т.62. №2. С.155-178. DOI: 10.33048/alglog.2023.62.201 РИНЦ
Dates:
| Submitted: | May 12, 2022 |
| Accepted: | Jan 31, 2024 |
| Published print: | Feb 13, 2024 |
| Published online: | Feb 13, 2024 |
Identifiers:
| Web of science: | WOS:001160582200001 |
| Scopus: | 2-s2.0-85185122495 |
| Elibrary: | 64812152 |
| OpenAlex: | W4391783264 |