Конечно порождённые структуры, вычислимые за полиномиальное время

Конечно порождённые структуры, вычислимые за полиномиальное время Full article

Journal

Сибирский математический журнал
ISSN: 0037-4474

Output data

Year: 2022, Volume: 63, Number: 5, Pages: 953-974 Pages count : 22 DOI: 10.33048/smzh.2022.63.501

Authors

Алаев П.Е. ¹

Affiliations

1	Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090

Funding (2)

1	Sobolev Institute of Mathematics	FWNF-2022-0011
2	Russian Foundation for Basic Research	20-01-00300

Получено простое описание конечно порождённых структур, обладающих изоморфным представлением, вычислимым за полиномиальное время (P-вычислимых). Описание близко к формулировке теоремы Дж. Реммела и Х. Фридмана. Доказано, что любая конечно порождённая подструктура P-вычислимой структуры также обладает P-вычислимым представлением. Полученное описание применяется к классам конечно порождённых полугрупп, групп, коммутативных колец с единицей и полей, а также упорядоченных коммутативных колец с единицей и полей. Доказано, что любое конечно порождённое коммутативное кольцо или поле обладают P-вычислимым представлением.

Алаев П.Е.
Конечно порождённые структуры, вычислимые за полиномиальное время
Сибирский математический журнал. 2022. Т.63. №5. С.953-974. DOI: 10.33048/smzh.2022.63.501 РИНЦ

Alaev P.E.
Finitely generated structures computable in polynomial time
Siberian Mathematical Journal. 2022. V.63. N5. P.801-818. DOI: 10.1134/S0037446622050019 WOS Scopus РИНЦ OpenAlex

Elibrary:

50514925

DB	Citing
Elibrary	3