1
$\begingroup$

In Sipser's book page 351:

Recall that Savitch's theorem shows that we can convert nondeterministic TMs to deterministic TMs and increase the space complexity $f(n)$ by only a squaring, provided that $f(n) \geq n .$ We can extend Savitch's theorem to hold for sublinear space bounds down to $f(n) \geq \log n .$ The proof is identical to the original one we gave on page $334,$ except that we use Turing machines with a read-only input tape; and instead of referring to configurations of $N,$ we refer to configurations of $N$ on $w .$ Storing a configuration of $N$ on $w$ uses $\log \left(n 2^{O(f(n))}\right)=\log n+$ $O(f(n))$ space. If $f(n) \geq \log n,$ the storage used is $O(f(n))$ and the remainder of the proof remains the same.

Later on he mentions:

To show that the reduction operates in log space, we give a log space transducer that outputs $\langle G, s, t\rangle$ on input $w .$ We describe $G$ by listing its nodes and edges. Listing the nodes is easy because each node is a configuration of $M$ on $w$ and can be represented in $c \log n$ space for some constant $c$.

My question is how exactly does a configuration get stored on the output tape? and how is it represented by a logarithmic term (does it differ between different encodings of a configuration)?

Also a small question, when talking about a machine's configuration on input $w$, do we actually mean configuration graph all inputs of length $|w|$? is that why $w$ is not part of the configuration graph?

$\endgroup$
  • $\begingroup$ Sipser probably defines what he means by configuration. It should consist of the state, the (modifiable) tapes, and the locations of the heads. $\endgroup$ – Yuval Filmus Feb 7 at 15:55
  • $\begingroup$ @YuvalFilmus He does indeed define it that way, after reading some more, I understood the general idea of the proof of, however, one thing is still confusing me, let $G$ be any graph, we want to check for a path $s-t$, we first construct the configuration graph, and then check for said path, I understood how the checking is done in log-space, but why is the construction is done in log-space? where does the graph gets stored for it to be checked? For example, reducing $2-SAT$ to PATH is done by constructing the graph and then checking for a path, but where does the actual graph gets stored? $\endgroup$ – user574362 Feb 7 at 16:10
  • $\begingroup$ You don't store the graph anywhere. You just need to be able to go over all neighbors of a vertex in logspace. $\endgroup$ – Yuval Filmus Feb 7 at 16:17
  • $\begingroup$ To elaborate more, lets say that I am using the adjacency matrix to encode a graph, and lets continue with the more simple $2SAT$ problem (my question is regarding the construction rather than the checking). The reduction used to build the appropriate graph is well-known, but what is the intuition behind it being in log-space. (Note that I used $2SAT$ instead of configuration graphs in order to focus more on the process of building the graph rather than deal with configurations graph) $\endgroup$ – user574362 Feb 7 at 16:18
  • $\begingroup$ You don't store the graph anywhere. You just need to be able to over all neighbors of a vertex in logspace. If you ask this question again (worded differently), you'll get exactly the same answer. You don't store the graph anywhere. You just need to be able to over all neighbors of a vertex in logspace. $\endgroup$ – Yuval Filmus Feb 7 at 16:18

Your Answer

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

Browse other questions tagged or ask your own question.