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