Рыбалов А. Н.
Сложность вычислений в алгебраических системах

В работе [1] впервые были рассмотрены вычислимость и сложность вычислений над полями вещественных и комплексных чисел. Этот подход был обобщен для произвольной алгебраической системы в [2]. В данной статье предлагается подход к теории сложности вычислений над произвольной алгебраической системой, в котором в качестве вычислительной модели взята вычислимость над списочной надстройкой, предложенная в [3]. Изучаются получающиеся классы полиномиальной сложности. Приводятся некоторые NP-полные проблемы.

Rybalov A. N.
Computational complexity in algebraic systems

Computability and computational complexity were first considered over the fields of real and complex numbers and generalized to arbitrary algebraic systems. This article approaches the theory of computational complexity over an arbitrary algebraic system by taking computability over the list extension for a computational model of it. We study the resultant polynomial complexity classes and mention some NP-complete problems.

Полный текст статьи / Full texts:

• PDF file (427 KB)
• PostScript file (835 KB)