Полиномиальная эквивалентность двух моделей вычислений в алгебраических системах

doi:10.17223/20710410/72/8

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Полиномиальная эквивалентность двух моделей вычислений в алгебраических системах	683 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/72/8

#алгебраические системы

#списочная надстройка

#S-вычислимость

Title: Полиномиальная эквивалентность двух моделей вычислений в алгебраических системах
Title: Polynomial equivalence of two models of computations in algebraic structures
Creator: Карацев, Никита Русланович
Date: 2026
DOI: 10.17223/20710410/72/8
Description: Изучаются две модели вычислимости над произвольной алгебраической системой U = (А, σ): 1) вычислимость над списочной надстройкой, предложенная И. В. Ашаевым, В. Я. Беляевым и А. Г. Мясниковым, и 2) S-вычислимость А. Хеммерлинга. Доказывается полиномиальная эквивалентность этих моделей для множества строк А+ над основным множеством A алгебраической системы U. Это означает, что любая функция f : А+ → А+, вычислимая за полиномиальное время в S-вычислимости, также вычислима за полиномиальное время над списочной надстройкой, и наоборот. В частности, это показывает, что аналоги класса сложности Р в этих двух моделях над строками А+ совпадают. То же самое имеет место и для аналогов класса NP. Полученные результаты можно использовать для оценки вычислительной сложности различных алгоритмов, написанных на языках программирования высокого уровня.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Relation: Прикладная дискретная математика
Type: статьи в журналах
Source: Прикладная дискретная математика. 2026. № 72. С. 103-116
Language: rus

Created: 03-06-2026

4 Visitors

4 Hits

0 Downloads

Журналы ТГУ Полиномиальная эквивалентность двух моделей вычислений в алгебраических системах