×

Monotonicity constraints in characterizations of PSPACE. (English) Zbl 1311.03067

Summary: A celebrated contribution of S. Bellantoni and S. Cook [Comput. Complexity 2, No. 2, 97–110 (1992; Zbl 0766.68037)] was a function algebra to capture FPTIME. This algebra uses recursion on notation. Later, I. Oitavem [Rev. Mat. Univ. Complutense Madr. 10, No. 1, 109–125 (1997; Zbl 0872.03028)] showed that including primitive recursion, an algebra is obtained that captures FPSPACE. The main results of this article concern variants of the later algebra. First, we show that iteration can replace primitive recursion. Then, we consider the results of imposing a monotonicity constraint on the primitive recursion or iteration. We find that in the case of iteration, the power of the algebra shrinks to FPTIME. More interestingly, with primitive recursion, we obtain a new implicit characterization of the polynomial hierarchy (FPH). The idea to consider these monotonicity constraints arose from the results on write-once tapes for Turing machines. We review this background and also note a new machine characterization of \(\Delta ^{P}_{2}\), that similarly to our function algebras, arises by combining monotonicity constraints with a known characterization of PSPACE.

MSC:

03D15 Complexity of computation (including implicit computational complexity)
03D20 Recursive functions and relations, subrecursive hierarchies
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D10 Turing machines and related notions
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI