1
$\begingroup$

We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says:

  • Let $L\in NPSPACE$.
  • Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that accepts $L$.
  • For every input word $w$, the number of vertices in the configuration graph of $M$ is exponential in $|w|$.
  • Nevertheless, using the algorithm from Savitch's proof, we can check whether there exists a path in the graph from the initial state to the accepting state, using space polynomial in $|w|$.

My problem is the memory required to store the graph. How can we store the graph using space polynomial in $|w|$?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You don't store the graph. You access it implicitly. This is exactly what happens in the proof of Savitch's theorem. $\endgroup$
    – Yuval Filmus
    Jul 24, 2019 at 16:21
  • $\begingroup$ @YuvalFilmus I understand this intuitively, mostly thanks to your answer, but I hoped for an explicit explanation about how we actually achieve that. If this is exactly the contents of the proof, then I guess I should just read the full proof (which we weren't shown in class (which isn't an excuse, of course)). $\endgroup$
    – Oren Milman
    Jul 24, 2019 at 16:37
  • 1
    $\begingroup$ Yes, reading the actual proof would be a great start. $\endgroup$
    – Yuval Filmus
    Jul 24, 2019 at 16:45

1 Answer 1

Reset to default
-2
$\begingroup$

I had the same thoughts when i did Complexity course myself. Its a very simple answer - the graph is stored on the tape and even though it is part of the input, its not calculated as part of the space complexity of the machine. This is by definition of space complexity analysis.

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.