zbMATH — the first resource for mathematics

Computational complexity in algebraic systems. (Russian, English) Zbl 1096.03046
Sib. Mat. Zh. 45, No. 6, 1365-1377 (2004); translation in Sib. Math. J. 45, No. 6, 1113-1123 (2004).
The author defines complexity notions for the approach to computability on abstract structures based upon BSS-machines acting over list extensions [I. V. Ashaev, V. Ya. Belyaev, and A. G. Myasnikov, Algebra Logic 32, No. 4, 183–205 (1993); translation from Algebra Logika 32, No. 4, 349–386 (1993; Zbl 0829.03023)]. The resulting polynomial complexity classes are studied. Some NP-complete problems are presented.
03D15 Complexity of computation (including implicit computational complexity)
03D75 Abstract and axiomatic computability and recursion theory
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: EMIS EuDML