Recursion-theoretic characterization of FPH

Isabel Oitavem


An algorithm working in polynomial space is allowed to reuse space, and if we look at known algorithms for PSPACE-complete problems, they always seem to rely heavily on this possibility. Our intuition then indicates that this is a crucial point concerning the problem PTIME versus PSPACE. A rigorous formulation of this intuition is the known fact that a "write-once" Turing machine, given polynomial space, decides exactly PTIME.
A write-once machine is one which is not allowed to erase (or rewrite) cells which have been previously written on.

Since the write-once restriction can, in some sense, be seen as a monotonicity constraint on the contents of the storage, this suggests investigating how sensitive characterisations of PSPACE are to "monotonicity constraints".

One explores, in particular, the interplay between recursion and iteration. We take as starting point a recursion-theoretic characterisation of FPSPACE, and we show that substituting predicative primitive iteration for predicative primitive recursion also leads to FPSPACE.

We show that imposing a monotonicity constraint on the above recursion and iteration operators leads, in the case of primitive iteration, to FPTIME, and, in the case of primitive recursion, to the polynomial hierarchy FPH. We form a hierarchy based on the nesting-level of the restricted primitive recursion operator, and this provides a new implicit characterisation of all levels of the polynomial hierarchy.
(joint work with Amir Ben-Amram and Bruno Loff)
Thursday 31st March 2011, 14:00
Far-134 (Video Conferencing Room)
Department of Computer Science