A teammate says a routine using only logarithmic memory might still churn for astronomically long on one fixed input; what does the space bound alone already prove about its running time?
answer
- count the snapshots, not the steps
- a snapshot is state plus heads plus tape
- deterministic repeat means never halting
- 2^O(s + log n) configurations
- log space therefore polynomial time
basics
~20 sA halting deterministic machine never repeats a configuration, and s work cells over an n-symbol input allow only about 2^O(s + log n) of them. Logarithmic space therefore forces polynomial time, so the teammate is wrong.
solid answer
~50 sThe bridge is **configuration counting**. A configuration is everything that determines the rest of the run: the control state, the input head position, the work head position, and the work tape's contents. With s work cells over an n-symbol input that is `|states| x (n+2) x s x |alphabet|^s`, which is `2^O(s + log n)`. Now the key step: a deterministic machine that ever revisits a configuration will repeat the identical steps forever, so a machine that halts visits each configuration at most once. Its running time is therefore bounded by the number of configurations. Put `s = O(log n)` in and the count is **polynomial in n**, so anything solvable in logarithmic space is solvable in polynomial time. The same count with `s` polynomial gives `2^(n^k)` steps, which is why polynomial space sits inside exponential time.
go deeper
Recall that a snapshot of a machine is finite: state, where each head sits, and what is on the work tape. Few possible snapshots means a short run.
Reproduce the count and the substitution: states times head positions times tape contents is 2^O(s + log n), which is polynomial when s is logarithmic. Say why a deterministic repeat means the machine never halts.
Use it as a review argument. When someone claims a tiny-memory component may run unboundedly long, you should be able to say what the memory ceiling already guarantees and where the guarantee stops, namely at termination.
The asymmetry is the strategic point: a deadline buys a memory bound of the same order, while a memory ceiling buys only an exponential time bound. Decide which side of that trade your contracts should sit on.
## What a configuration is A **configuration** is a complete snapshot of the machine at one instant — everything that determines what happens next, and nothing else. On the machine used for space bounds (a read-only input tape of n symbols, a read-write work tape of s cells) it is exactly four things: 1. the **control state**, drawn from a fixed finite set that does not grow with the input; 2. the **input head position**, one of n+2 places counting the two end markers; 3. the **work head position**, one of s places; 4. the **contents of the work tape**, a string of s symbols over a fixed alphabet. Nothing else is needed. The input itself is not part of the configuration because it never changes, and the machine can always look at it again. ## Counting them Multiplying the independent choices: `configurations = |states| x (n+2) x s x |alphabet|^s` The first factor is a constant. The second and third are polynomial in n (with s itself at most polynomial). The last is the one that dominates: it is exponential in s. Collecting the whole product into an exponent gives `configurations = 2^O(s + log n)` and every conclusion in this leaf falls out of that single expression by substituting a value for s. ## Why a halting machine cannot beat the count Here is the step the question is really probing, and it takes one line: 1. The machine is **deterministic**: the configuration alone decides the next configuration. 2. So if the run ever reaches the same configuration twice, everything between those two visits repeats, forever, identically. 3. A run that repeats forever does not halt. Therefore a halting run visits each configuration **at most once**. 4. Its number of steps is at most the number of configurations. That is why the teammate's picture is wrong. A logarithmic-space routine can certainly run far longer than a single scan of the input — it may sweep the archive again and again — but *astronomically* long is not available to it. Its budget is capped by a polynomial. ## What the bound gives at each size of s | work space s(n) | configuration count | time bound for a halting run | |---|---|---| | O(log n) | polynomial in n | polynomial — logarithmic space sits inside polynomial time | | polynomial n^k | 2^O(n^k) | exponential — polynomial space sits inside exponential time | | 2^O(n^k) | doubly exponential | the same pattern one level up | The first row is the one people quote. The reason it holds is this count, not any simulation of nondeterminism: a deterministic logspace machine simply cannot afford enough distinct snapshots to run longer. ## The direction the implication runs Both directions exist, and they are not equally interesting. - **Space to time:** a bound of s work cells gives a time bound of `2^O(s + log n)`. This is a genuine bound but an extravagantly loose one whenever s is large. - **Time to space:** a bound of t steps gives a space bound of about t cells, because each step writes at most one cell. This is tight and cheap. So a memory ceiling is the more *constraining* promise: it costs a lot to give, and what it hands back in time is enormous. A deadline is the more *informative* promise, since it pins memory to the same order for free. ## What the count does not say - It says nothing about a machine that does **not** halt. A logspace machine may loop forever; the theorem is conditional on termination, and detecting that case is a different subject entirely. - It is not a *lower* bound. A logspace routine may well finish in one linear pass; the count only caps how bad it can be. - It does not transfer the tightness. Knowing a routine is polynomial-time because it is logspace tells you nothing about which polynomial, and the bound from the count is usually far above the truth. - For a nondeterministic machine the same snapshot count still applies, but the argument changes shape: instead of a single run that cannot repeat, you reason about a graph on those polynomially many configurations and ask whether the accepting one is reachable. That graph view is what places nondeterministic logarithmic space inside polynomial time. The practical residue for an engineer is a rule of thumb worth having: **a hard, small memory ceiling on a terminating computation is implicitly a time bound too**, while a generous memory ceiling implies a time bound so weak it is not worth writing down.
- What happens to the argument if the machine does not halt?It simply does not apply. The bound is conditional on termination: a non-halting deterministic run is precisely one that revisits a configuration and then cycles through the same snapshots forever. Space bounds constrain how many distinct snapshots exist, not whether the machine ever stops.
- Why is the configuration count the reason logarithmic space sits inside polynomial time, rather than any nondeterminism result?Because the count is direct: polynomially many snapshots and no repeats give a polynomial step budget. The deterministic simulation of nondeterministic space squares the space instead, which for logarithmic space yields log-squared space and a quasi-polynomial time bound — weaker than what the count already gives.
- Does a time bound imply a space bound in the same way?Yes, and far more tightly. A run of t steps writes at most one cell per step, so it uses at most about t cells. The two implications are lopsided: time bounds memory at the same order, while memory bounds time only exponentially.
saying these in an interview costs you the question
- Thinks a small memory bound places no limit at all on running time
- Claims the count proves polynomial time even for a machine that loops
- Counts only the work tape contents and omits the head positions
- Says polynomial time implies logarithmic space, reversing the containment
- Treats the derived time bound as an estimate of real running time