Does iterated PSPACE trace equal ELEMENTARY?

Question

I have the following feeling (I wouldn't even call it a conjecture yet) which I'd like to ask whether it's true in some form.

Take the class of all programs running in polynomial space.

Surprisingly or not, they can still output an exponentially large output: at each step of their running they may output something, and since they may perform 2^poly(n) steps, they may output such a large output as well.

Now suppose we take this output and feed it again to a PSPACE machine, and so on. It can also be seen as inputing to one PSPACE Turing machine the trace (if we don't like the idea of outputting outside of the tape) of the running of another PSPACE Turing machine, which again might be exponential in size wrt the original input's size.

By that, do we cover the whole ELEMENTARY complexity class? If not, then any known class? It seems to me obviously beyond PSPACE and EXPSPACE or even n-EXPSPACE if we allow n+1 such iterations.

---

As per D.W.'s request, here's a more precise formulation of the question. Consider the class consisting of all possible pairs of PSPACE Turing machines. We consider running the pair of machines as follows. One machine takes an input and runs, and the second machine takes as input the trace of the running of the first machine. Which complexity class would this capture? It seems to me like EXPSPACE. Similarly if we took a triple of machines, two as above, and the third taking the trace of the second, it'd look to me like 2-EXPSPACE. Is that the situation indeed? What would be the computational power (in terms of complexity classes) of such iterated two (or more) different machines, one taking as input the trace of the other?

---

I guess that if this is correct and two iterated PSPACE machines capture EXPSPACE or beyond, then it'll prove that P!=PSPACE. So either it's all wrong and one can show me why it's wrong, or maybe even if it's right it doesn't actually imply P!=PSPACE.

Answer 1

Let's show that a single iteration captures EXPSPACE; the general case is similar.

It is clear that if you feed the output of a PSPACE algorithm to another PSPACE algorithm, then you get an EXPSPACE algorithm. In the other direction, let $L$ be a problem in EXPSPACE, say taking space $2^{p(n)}$. We run a PSPACE machine which pads the input with $2^{p(n)}$ zeroes (we can do this since we can count up to $2^{p(n)}$ using $p(n)$ space), and then feed the output to a PSPACE machine which first erases the padding and then transfers control to an EXPSPACE machine for $L$.

Answer 2

Yup. If you have two algorithms $A,A'$ both in PSPACE, and you run $A'$ on the output from $A$, the resulting algorithm is in EXPSPACE. Think about it: how much space is used by them together? Well, it's the amount of space for $A$, plus the amount of space for $A'$. If the input is length $n$, then the output of $A$ is at most $2^{p(n)}$, so the amount of space used by $A'$ is $q(2^{p(n)}$, where $p,q$ are polynomials. Thus the computation is in EXPSPACE.

Also, any computation in EXPSPACE can be expressed in this way. Suppose you have any language that can be computed in EXPSPACE, i.e., in $2^{p(n)}$ space. Then you can take $A$ to copy its input to the output, then output a string of $2^{p(n)}$ 1's; then $A'$ can do the computation itself, and since the input to $A'$ has length $2^{p(n)}$, $A'$ will use space polynomial (in fact linear) in its input length.

You are also correct about the iteration of three of these; the result is in 2-EXPSPACE.