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|$?

  • 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$ Jul 24 '19 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$ Jul 24 '19 at 16:37
  • 1
    $\begingroup$ Yes, reading the actual proof would be a great start. $\endgroup$ Jul 24 '19 at 16:45

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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