Recall the relationship between time and space; in particular:

“space is more valuable than time.” On time vs. space \begin{equation} \text{TIME}\left(\left(n\right)\right) \subseteq \text{SPACE} \left( \frac{t\left(n\right)}{\log \left(t\left(n\right)\right)}\right) \end{equation}

that is: space is strictly more valuable than time. Oh, and also:

Key idea: let’s transform the previous thing into a graph problem! Suppose M is the time T truing machine, and consider its configure at time t < T. Key idea: we can tradeoff time for space! notably, we will solve the same problem using a different algorithm, not modify the original machine. Intuition: as we prod along on our space, if an oracle showed up and told you some space was no longer relevant, you could just dealloc it to save space. . Let’s formalize this. Epochs Divide total time T used up into blocks of size B = \sqrt{T}. Each chunk is an “epoch of time” worth \sqrt{T}, and total number of epochs is also \sqrt{T}. We now state without proof: A TM is block respecting such that, within an epoch of time, its tape heads are confined to a fixed block of tape; it could cross and return to the same blocks during epoch boundaries. Different tapes could also use different blocks. WLOG, we can assume that our Turing machine is \sqrt{T} block respecting. The sketch of this proof is essentially just to make the Turing machine wait a little bit if it has to cross block boundaries. Insight: “can we delete the contents of the relevant blocks of epoch 17 after epoch 17?” To remember the final contents for k tapes, with each of the blocks being \sqrt{T} size, we have:

This means that naively, remembering everything doesn’t work, because we have \sqrt{T} such epochs, so we need \sqrt{T}^{2} = T. But! Turns out, we really only have to remember \frac{v}{\log v} many epochs to be able to recover the computation—that’s Hop croft Paul Valiant. Graph Theory Time! This reduces to a graph theory problem!! Let’s associate a directed graph G against our time T Turing Machine with v = \sqrt{T} vertices each representing time; one for each epoch. For each of the k tapes, add i \to j edge where j the next epoch that visits the relevant block of this tape. Observe: to simulate epoch j, it suffices to remember the final block contents of epoch i for all i such that i \to j is an edge. pebble game Solo game, played on an v vertex directed graph with source and sink. Goal: place pebble on sink; minimize the number of pebbles used ever on the graph. Rules: Start with a pebble on the source We can only place a pebble on vertex j if all of j’s predecessors have pebbles on them You can always remove any pebble HPV The original strategy for this was non-constructive. We’ll show constructive strategy that uses O\left(\frac{N \log \log v}{\log v}\right). Cook gave a lower bound \sqrt{v}. Let G be v vertex digraph with constant in-degree; then there is a pebbling strategy that uses O\left(\frac{v}{\log v}\right) pebbles. Pebbling Theorem G = constant degree (every node has the same degree) v-vertex graph; there’s a pebbling strategy for G using \leq O\left(\frac{v}{\log v}\right) pebbles. More generally, for a k degree graph, we have O\left( \frac{k v \log \log v}{\log v}\right). We state without proof the following theorem. Valiant’s Depth Reduction Lemma The depth of a digraph is the length of its longest path. Let G be a v vertex, m edge, depth d graph. For any parameter 1 \leq r \leq \log d, we can… reduce the depth to at most \leq \frac{d}{2^{r}} by deleting \frac{r}{\log d} \cdot m edges “by snipping away a few edges, there are no more long paths”. We proof of the Pebbling Theorem Our goal is to show that exists subset P of vertices such that |P| \leq O\left( \frac{v \log \log v}{\log v}\right) any path that doesn’t involve the set P has length \leq O\left(\frac{v}{\log v}\right) = l If we can show that we can pebble actually all of P^{*} = P \cup \left\{\text{sink}\right\}; we are done if we could do this since the sink is in P^{ *}. Our strategy is as follows— topologically sort P^{*} = u_1, u_2, …, u_{|p^{*}|} for i = 1,2, …, |P^{*}|, we apply strategy u_{i} After pebbling u_{i}, we will keep our pebble onto the thing. In essence in between u_{i} barriers, we pebble lengths of l and then use the pebbles.