3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Hint: Use Savitch's theorem to show that PSPACE=NPSPACE.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.