Сложность операции обращения в группах | Sciact - Система учета научной деятельности ИМ СО РАН

Сложность операции обращения в группах Научная публикация

Журнал

Алгебра и логика
ISSN: 0373-9252

Вых. Данные

Год: 2023, Том: 62, Номер: 2, Страницы: 155-178 Страниц : 24 DOI: 10.33048/alglog.2023.62.201

Ключевые слова

вычислимая группа, операции обращения, примитивно рекурсивная функция, фактор-структура

Авторы

Алаев П.Е. ¹

Организации

1	Ин-т матем. им. С.Л.Соболева СО РАН

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0011

Доказывается, что если 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-вычислимой структуре.

Алаев П.Е.
Сложность операции обращения в группах
Алгебра и логика. 2023. Т.62. №2. С.155-178. DOI: 10.33048/alglog.2023.62.201 РИНЦ

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

Поступила в редакцию:	12 мая 2022 г.
Принята к публикации:	31 янв. 2024 г.
Опубликована в печати:	18 февр. 2024 г.
Опубликована online:	18 февр. 2024 г.

РИНЦ:

60196145

Пока нет цитирований