Polynomial equivalence of two models of computations in algebraic structures Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Output data | Year: 2026, Number: 72, Pages: 103-116 Pages count : 14 DOI: 10.17223/20710410/72/8 | ||
| Tags | алгебраические системы, списочная надстройка, S-вычислимость. | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 25-11-20023 |
Abstract:
Изучаются две модели вычислимости над произвольной алгебраической системой U = (А, σ): 1) вычислимость над списочной надстройкой, предложенная И. В. Ашаевым, В. Я. Беляевым и А. Г. Мясниковым, и 2) S-вычислимость А. Хеммерлинга. Доказывается полиномиальная эквивалентность этих моделей для множества строк А+ над основным множеством A алгебраической системы U. Это означает, что любая функция f : А+ → А+, вычислимая за полиномиальное время в S-вычислимости, также вычислима за полиномиальное время над списочной надстройкой, и наоборот. В частности, это показывает, что аналоги класса сложности Р в этих двух моделях над строками А+ совпадают. То же самое имеет место и для аналогов класса NP. Полученные результаты можно использовать для оценки вычислительной сложности различных алгоритмов, написанных на языках программирования высокого уровня.
Cite:
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
Polynomial equivalence of two models of computations in algebraic structures
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2026. №72. С.103-116. DOI: 10.17223/20710410/72/8 OpenAlex
Dates:
| Published online: | Jun 29, 2026 |
Identifiers:
| ≡ OpenAlex: | W7165762860 |