Polynomial space complexity with exponential size witnesses Define the complexity class $C$ to be the class of all languages that can be verified by a TM that has:


Input tape: Read only, move in both directions.
Witness tape: Read only, move only in one direction.
Work tape: Read-Write, move in both directions.


The machine itself is deterministic (the guesses are the value of the witness tape). The space complexity is the size of the work tape, and is polynomial. We say the machine
accepts an input if and only if there exists a setting for the witness tape, with which the
machine accepts.

Prove: $C = \mathrm{PSPACE}$

Well, it's obvious that $\mathrm{PSPACE} \subset C$ since any TM $M$ can be converted into a TM $M'$ that simply ignores its witness tape and runs in the same space complexity as $M$.

However, I'm struggling with the other direction. The problem is that the witness can be exponential in the input and I can't see how we can enumerate over all witnesses using only polynomial space.

edit: I had a mistake, the witness tape can only be read in one direction.
Hint: Use Savitch's theorem to show that PSPACE=NPSPACE.