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