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