On the class of Skolem elementary functions. (Russian) Zbl 1249.03080

Summary: Under consideration are some equivalent definitions of the class of Skolem elementary functions (analogous to the known definitions of the class of Kalmar elementary functions) and some results for this class obtained by various mathematicians. The definitions of this class were studied independently of each other, and their equivalence is proved in this paper. We study the question of the existence of finite superposition bases in this class. We prove that the problem of the existence of such a basis amounts to a well-known problem from the theory of computational complexity.


03D20 Recursive functions and relations, subrecursive hierarchies
03D15 Complexity of computation (including implicit computational complexity)