# Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem

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

• You don't store the graph. You access it implicitly. This is exactly what happens in the proof of Savitch's theorem. – Yuval Filmus Jul 24 '19 at 16:21
• @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)). – Oren Milman Jul 24 '19 at 16:37
• Yes, reading the actual proof would be a great start. – Yuval Filmus Jul 24 '19 at 16:45