Сложность операции обращения в группах Full article
| Journal |
Алгебра и логика
ISSN: 0373-9252 |
||
|---|---|---|---|
| Output data | Year: 2023, Volume: 62, Number: 2, Pages: 155-178 Pages count : 24 DOI: 10.33048/alglog.2023.62.201 | ||
| Tags | вычислимая группа, операции обращения, примитивно рекурсивная функция, фактор-структура | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0011 |
Abstract:
Доказывается, что если A=(A,⋅) - группа, вычислимая за полиномиальное время (P-вычислимая), то существует P-вычислимая группа B=(B,⋅)≅A, в которой операция x−1 тоже P-вычислима. С другой стороны, доказывается, что если центр Z(A) группы A содержит элемент бесконечного порядка, то при некоторых дополнительных условиях существует P-вычислимая группа B′=(B′,⋅)≅A, в которой операция x−1 не является примитивно рекурсивной. Устанавливается также общий факт из теории P-вычислимых структур: если A - P-вычислимая структура, и E⊆A2 - P-вычислимая конгруэнция в A, то фактор-структура A/E изоморфна некоторой P-вычислимой структуре.
Cite:
Алаев П.Е.
Сложность операции обращения в группах
Алгебра и логика. 2023. Т.62. №2. С.155-178. DOI: 10.33048/alglog.2023.62.201 РИНЦ
Сложность операции обращения в группах
Алгебра и логика. 2023. Т.62. №2. С.155-178. DOI: 10.33048/alglog.2023.62.201 РИНЦ
Translated:
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
Dates:
| Submitted: | May 12, 2022 |
| Accepted: | Jan 31, 2024 |
| Published print: | Feb 18, 2024 |
| Published online: | Feb 18, 2024 |
Identifiers:
| Elibrary: | 60196145 |
Citing:
Пока нет цитирований