|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
Конечно порожденные структуры, вычислимые за полиномиальное время
П. Е. Алаев Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
Аннотация:
Получено простое описание конечно порожденных структур, обладающих изоморфным представлением, вычислимым за полиномиальное время (P-вычислимых). Описание близко к формулировке теоремы Реммела и Фридмана. Доказано, что любая конечно порожденная подструктура P-вычислимой структуры также обладает P-вычислимым представлением. Полученное описание применяется к классам конечно порожденных полугрупп, групп, коммутативных колец с единицей и полей, а также упорядоченных коммутативных колец с единицей и полей. Доказано, что любое конечно порожденное коммутативное кольцо или поле обладают P-вычислимым представлением.
Ключевые слова:
вычислимые структуры, полиномиальная вычислимость, сложность алгоритма, полугруппы, группы, кольца, поля.
Статья поступила: 18.12.2021 Окончательный вариант: 23.04.2022 Принята к печати: 15.06.2022
Образец цитирования:
П. Е. Алаев, “Конечно порожденные структуры, вычислимые за полиномиальное время”, Сиб. матем. журн., 63:5 (2022), 953–974; Siberian Math. J., 63:5 (2022), 801–818
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj7706 https://www.mathnet.ru/rus/smj/v63/i5/p953
|
Статистика просмотров: |
Страница аннотации: | 126 | PDF полного текста: | 36 | Список литературы: | 29 | Первая страница: | 7 |
|