Polynomial equivalence of two models of computations in algebraic structures | Sciact - Система учета научной деятельности ИМ СО РАН

Polynomial equivalence of two models of computations in algebraic structures Научная публикация

Журнал

Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263

Вых. Данные

Год: 2026, Номер: 72, Страницы: 103-116 Страниц : 14 DOI: 10.17223/20710410/72/8

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

алгебраические системы, списочная надстройка, S-вычислимость.

Авторы

Karatsev Nikita R. ¹

Организации

1	Omsk branch of Sobolev Institute of Mathematics SB RAS

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

Российский научный фонд

25-11-20023

Изучаются две модели вычислимости над произвольной алгебраической системой U = (А, σ): 1) вычислимость над списочной надстройкой, предложенная И. В. Ашаевым, В. Я. Беляевым и А. Г. Мясниковым, и 2) S-вычислимость А. Хеммерлинга. Доказывается полиномиальная эквивалентность этих моделей для множества строк А+ над основным множеством A алгебраической системы U. Это означает, что любая функция f : А+ → А+, вычислимая за полиномиальное время в S-вычислимости, также вычислима за полиномиальное время над списочной надстройкой, и наоборот. В частности, это показывает, что аналоги класса сложности Р в этих двух моделях над строками А+ совпадают. То же самое имеет место и для аналогов класса NP. Полученные результаты можно использовать для оценки вычислительной сложности различных алгоритмов, написанных на языках программирования высокого уровня.

Karatsev N.R.
Polynomial equivalence of two models of computations in algebraic structures
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2026. №72. С.103-116. DOI: 10.17223/20710410/72/8 OpenAlex

Опубликована online:

29 июн. 2026 г.

≡ OpenAlex:

W7165762860