|
Sibirskii Matematicheskii Zhurnal, 2004, Volume 45, Number 6, Pages 1365–1377
(Mi smj1146)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Computational complexity in algebraic systems
A. N. Rybalov Omsk State University
Abstract:
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.
Keywords:
generalized computability, computational complexity.
Received: 20.04.2004
Citation:
A. N. Rybalov, “Computational complexity in algebraic systems”, Sibirsk. Mat. Zh., 45:6 (2004), 1365–1377; Siberian Math. J., 45:6 (2004), 1113–1123
Linking options:
https://www.mathnet.ru/eng/smj1146 https://www.mathnet.ru/eng/smj/v45/i6/p1365
|
|