Why does logarithmic space, the class L, charge only a work tape and never the read-only input a machine scans?

## The model the bound is defined on A space bound is a claim about one specific machine, and the accounting only makes sense once that machine is on the table. The machine used to define logarithmic space has three tapes with three different roles: - a **read-only input tape** holding the n symbols of the instance. The head moves in both directions and may revisit any cell any number of times, but no cell can be altered. - a **read-write work tape**, initially blank. The number of cells it ever touches is the machine's space usage, and the only thing counted. - a **write-only output tape** for machines that emit an answer longer than a yes/no. Its head only moves forward, it is never read back, and it is not counted either. A machine *runs in space s(n)* when, on every input of length n, it uses at most s(n) work cells. **L** is the set of decision problems solvable this way with s(n) = O(log n) by a deterministic machine. **NL** is the same tape arrangement with a machine whose transition may branch, accepting when some branch accepts. ## Why the input is not charged Three reasons, and the third is the one that gives the class its character. 1. The input is already in memory before the computation begins. It is the question, not the answer's scratch space, and every model charges for what the algorithm *creates*. 2. If the input were charged, every machine would cost at least n cells, every problem would sit in linear space, and there would be no sublinear range in which to distinguish anything. The interesting question — can you solve this with a few pointers, or must you build a structure proportional to the data? — would have no home. 3. Because re-reading is free, the accounting *forces recomputation*. A routine that cannot afford to remember what it saw must walk back and look again. That is the behaviour the class is designed to isolate. | tape | direction | writable | counted | |---|---|---|---| | input | both ways, unlimited re-reads | no | no | | work | both ways | yes | **yes — this is the bound** | | output | forward only | write-only | no | ## What O(log n) cells actually buy Addressing arithmetic decides this. A position in an n-symbol input is a number below n, which needs about `log2 n` bits. So a logarithmic work tape holds: - a **constant number of indices** into the input — the equivalent of a handful of pointers you may move around at will; - **counters** bounded by n, or by any fixed power of n, since k·log n is still O(log n); - a constant number of symbols copied out of the input, such as the value currently under a pointer. It does **not** hold: any constant fraction of the input, a set of the distinct values seen so far, a lookup structure keyed by input values, or any tally whose count of *entries* grows with n. A structure with n entries needs at least n cells no matter how small each entry is. So the honest one-line translation is: *a logspace routine is a handful of pointers and counters over data it must revisit rather than store.* ## Free re-reading is not a single pass This is the most common confusion in the area. A one-pass streaming algorithm with O(log n) memory is a **strictly stronger** commitment: it sees each symbol once, in order, and cannot go back. A logspace machine may sweep the input left to right, then right to left, then jump to a position it computed, as many times as it likes — the only thing it may not do is write any of it down beyond its few cells. Many problems are easy for one and hopeless for the other. ## L, NL, and the example the class is built around The reserved illustration for this pair is reachability on a graph presented in the input. Asking whether one node reaches another along directed edges is the signature problem of **NL**: a guessing machine walks from the start node, holding only the current node's index and a step counter, guessing which edge to take next — two counters, nothing else. The deterministic version is the harder question. For undirected edges, a much later result placed the problem in **L**. Whether the guessing helps in general — whether L and NL differ — is a question about the inclusion chain rather than about the model, and it is not settled by anything in the accounting above. The practical shape of all this is a tool that scans an enormous read-only archive through a fixed buffer it may never grow: it may pass over the archive as often as the clock allows, and what it can decide is exactly what a few pointers and counters can decide.