Complexity of the inversion operation in groups Научная публикация
| Журнал |
Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302 |
||
|---|---|---|---|
| Вых. Данные | Год: 2023, Том: 62, Номер: 2, Страницы: 103-118 Страниц : 16 DOI: 10.1007/s10469-024-09730-9 | ||
| Ключевые слова | computable group, inversion operations, primitive recursive function, quotient structure | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0011 |
Реферат:
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.
Библиографическая ссылка:
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
Оригинальная:
Алаев П.Е.
Сложность операции обращения в группах
Алгебра и логика. 2023. Т.62. №2. С.155-178. DOI: 10.33048/alglog.2023.62.201 РИНЦ
Сложность операции обращения в группах
Алгебра и логика. 2023. Т.62. №2. С.155-178. DOI: 10.33048/alglog.2023.62.201 РИНЦ
Даты:
| Поступила в редакцию: | 12 мая 2022 г. |
| Принята к публикации: | 31 янв. 2024 г. |
| Опубликована в печати: | 13 февр. 2024 г. |
| Опубликована online: | 13 февр. 2024 г. |
Идентификаторы БД:
| Web of science: | WOS:001160582200001 |
| Scopus: | 2-s2.0-85185122495 |
| РИНЦ: | 64812152 |
| OpenAlex: | W4391783264 |