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
03D15 Complexity of computation (including implicit computational complexity)
03D20 Recursive functions and relations, subrecursive hierarchies
68Q25 Analysis of algorithms and problem complexity