|
Сибирский математический журнал, 2004, том 45, номер 6, страницы 1365–1377
(Mi smj1146)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Сложность вычислений в алгебраических системах
А. Н. Рыбалов Омский государственный университет им. Ф. М. Достоевского
Аннотация:
В работе [1] впервые были рассмотрены вычислимость и сложность вычислений над полями вещественных и комплексных чисел. Этот подход был обобщен для произвольной алгебраической системы в [2]. В данной статье предлагается подход к теории сложности вычислений над произвольной алгебраической системой, в котором в качестве вычислительной модели взята вычислимость над списочной надстройкой, предложенная в [3]. Изучаются получающиеся классы полиномиальной сложности. Приводятся некоторые $NP$-полные проблемы.
Ключевые слова:
обобщенная вычислимость, сложность вычисления.
Статья поступила: 20.04.2004
Образец цитирования:
А. Н. Рыбалов, “Сложность вычислений в алгебраических системах”, Сиб. матем. журн., 45:6 (2004), 1365–1377; Siberian Math. J., 45:6 (2004), 1113–1123
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj1146 https://www.mathnet.ru/rus/smj/v45/i6/p1365
|
Статистика просмотров: |
Страница аннотации: | 284 | PDF полного текста: | 105 | Список литературы: | 51 |
|