Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Monotonicity conditions over characterisations of PSPACE

Edit abstract data

Speaker: Bruno Loff
Author(s): Bruno Loff and Isabel Oitavem
Slot: Wed, 17:10-17:30, Room 19 (col. 5)


It is an open problem whether P = PSPACE. An algorithm working in
polynomial space is allowed to erase previously used cells in order
to reuse space, and if we observe the well-known algorithms for
PSPACE-complete problems, they always seem to rely heavily on this
possibility. Our intuition then indicates that this is the crucial
difference between P and PSPACE. In this presentation, we begin by
making this intuition rigourous, by proving that the additional power
of PSPACE arises exactly from the fact that we are allowed to reuse
space. We consider a ?write-only? Turing machine, given polynomial
space, which is not allowed to erase (or re-write over) cells which
have been previously written on; we then prove that under this
restriction, polynomial-space-bounded Turing machines decide exactly P.

This will lead us to consider weaker forms of this "write-only"
restriction. Consider the natural partial order over binary strings,
where w < v if |w| < |v| or if each symbol of w is not greater than
each symbol of v in the same position. Then by a detailed observation
of the tape configurations of a write-only machine we find that
consecutive tape configurations are monotonically increasing
according to this order. It turns out that this monotonicity ensures
that any set decided by a monotone polynomial-space bounded
computation can also be decided in P. Then P vs. PSPACE is equivalent
to asking whether a polynomial-space-bounded computation can be made

So in the second part of our presentation we apply these results to
implicit characterisations of PSPACE.  We introduce two multi-sorted
function algebras A and B.  A is, essentially, the characterisation
of FPSPACE given by Isabel Oitavem in 97, and B is A with the
input-sorted primitive recursion replaced by input-sorted primitive
iteration. We show that, analogously to A, B characterises PSPACE.
When we restrict the recursion and iteration operators to functions
obeying a monotonicity condition, we obtain two algebras A' and B'.
A' is obtained by restricting input-sorted primitive recursion, and
B' by restricting input-sorted iteration. Our results are that B'
characterises P, A' characterises the polynomial hierarchy, and if we
consider a hierarchy A'_1, ..., A'_n, ... by counting the rank of the
operator of restricted input-sorted primitive recursion, then A'_n
corresponds to the functions computable with oracles in (Sigma_n
intersect Pi_n) for all n. The whole work suggest a new machine-based
characterisation of PH and of each level (Sigma_n intersect Pi_n) by
polynomial-space write-only deterministic machines coupled with

websites: Arnold Beckmann 2008-05-29 Valid HTML 4.01! Valid CSS!