# zbMATH — the first resource for mathematics

The characterization of some complexity classes by recursion schemata. (English) Zbl 0615.03025
Theory of algorithms, Colloq. Pécs/Hung. 1984, Colloq. Math. Soc. János Bolyai 44, 313-322 (1986).
[For the entire collection see Zbl 0592.00028.]
Two modifications of ordinary recursion schemata, namely simultaneous limited recursion schemata (sim-LRS) and short limited recursion schemata (sho-LRS) are considered. The following recursion-theoretic characterization of space and time complexity classes for Turing machines is given. Let $$A=\{x+1$$, max(x,y), $$I^ m_ n\}$$ and $$B=A\cup \{x\dot- y$$, [x/y]$$\}$$ where $$I^ m_ n(x_ 1,...,x_ n)=x_ m$$. For a class of functions S, let $$E^ S$$ (resp. $$F^ S)$$ denote the least class containing A (resp. B) and the function $$2^{s(| x|)}$$ for $$s\in S$$ and closed under the operation of substitution and sim-LRS (resp. sho-LRS). Then for any ”reasonable” class of functions S it holds that $$E^ S=DSPACE(S)$$ and $$F^ S=DTIME(S)$$.
Reviewer: S.P.Yukna
##### MSC:
 03D15 Complexity of computation (including implicit computational complexity) 03D20 Recursive functions and relations, subrecursive hierarchies 68Q25 Analysis of algorithms and problem complexity