A long-running archive scanner can contractually promise a fixed memory ceiling or a wall-clock deadline; how do you decide which bound to own?
answer
- the two bounds are not symmetric
- time bounds memory at the same order
- memory bounds time only exponentially
- only a tiny ceiling implies fast
- enforceable ceiling, best-effort latency
basics
~20 sDecide by what each bound implies. A deadline hands you a memory bound of the same order for free; a memory ceiling hands back only an exponential time bound. Promise memory when the problem's time cost is unknown, and time when its complexity is.
solid answer
~50 sThe two bounds are not symmetric. A promise of `t` steps already implies at most about `t` cells, because a step writes at most one cell — so a deadline carries a usable memory bound with it. A promise of `s` cells implies only `2^O(s + log n)` steps, from counting configurations, which is a real bound and a worthless one for anything but a very small `s`. Two consequences follow. If the work is known to be in polynomial time with a known degree, the **deadline** is the defensible promise and memory follows. If the work is only known to fit in polynomial space — a planner, an adversarial "can I always respond" check — then the **memory ceiling** is the only bound you can actually hold, and the honest latency contract is best-effort with an interruptible result. There is also an operational difference: a memory ceiling fails loudly, locally and immediately, whereas a missed deadline leaves a partial answer and a caller to compensate.
go deeper
Recall which way the implications run: a step writes at most one cell, so a time limit caps memory at the same order, while a memory limit caps time only by an enormous exponential.
Explain where each bound comes from — one cell per step in one direction, the configuration count in the other — and why only a very small ceiling yields a time bound anyone would use.
Show the operational difference. A memory ceiling fails immediately and locally, a missed deadline leaves a partial result and an ambiguous owner, and that shapes what callers can be asked to handle.
Own the asymmetry in the contract itself: make the enforceable bound the guarantee, make the other a target with a stated degradation path, and be able to say what is known about the problem that justifies which is which.
## The two implications, side by side Everything in this decision comes from two facts about how the resources bound each other, and they are lopsided. | you promise | what it implies for the other resource | how useful is that | |---|---|---| | `t` steps | at most about `t` work cells, since each step writes at most one | tight and immediately usable | | `s` work cells | at most `2^O(s + log n)` steps, from the configuration count | true, but astronomically loose unless `s` is tiny | The asymmetry has a one-line cause: **memory is reusable and time is not.** A cell overwritten is a cell you get back; a step spent is gone. So a computation may sit inside a modest memory ceiling forever, and a memory promise cannot by itself keep a latency promise. The one place where the second row is genuinely informative is at the bottom of the scale. A **logarithmic** ceiling forces a polynomial number of steps, because the configuration count is then polynomial. That is why a scanner designed around a handful of pointers and counters over a read-only archive has both bounds at once, and it is the strongest version of the memory promise available. ## What each bound is like to own - **A memory ceiling is enforceable and observable.** The process either fits or it does not; the platform enforces it whether or not you do, and a violation is immediate, local and attributable. - **A memory ceiling is also a design constraint, not a runtime knob.** Meeting it may mean replacing retention with recomputation — extra passes over the archive rather than a structure held in the buffer. That cost lands in latency, which is the resource you did not promise. - **A deadline depends on things outside the algorithm**: the hard instance, contention, the state of whatever it reads. It is a statistical promise dressed as an absolute one unless you know the complexity of the work. - **A deadline fails softly and ambiguously.** The output is partial, the caller must decide whether to retry or degrade, and the failure is usually attributed to the wrong component. ## How the decision actually goes 1. **Establish what is known about the work itself.** If the task has a known polynomial time bound with a known degree and an input size you control, a deadline is defensible and the memory bound comes along with it at the same order. 2. **If the task is only known to fit in polynomial space** — anything with the alternating "for every possible reply" structure, for instance — then no honest deadline exists, because the only time bound anyone can prove is exponential in the space used. Promise the ceiling. 3. **If the task can be pushed down to a few counters and pointers over a read-only input**, promise the small ceiling and get the polynomial time bound free. This is worth real design effort precisely because it is the one case where the memory promise implies a useful time promise. 4. **Decide the failure mode you want to hand callers.** An interruptible computation that can return a usable partial answer converts a missed deadline into a degraded result; a computation that only produces an answer at the end cannot. ## The trap in this decision The common mistake is to read "fits in polynomial space" as reassurance about running time. It is the opposite of reassurance: it says the computation will fit in memory while exploring a space that may be exponentially large, and the whole reason such a computation can be written at all is that it reuses the same cells across an enormous number of possibilities. A team that sizes hardware from the memory bound and then quietly expects proportional latency has drawn the wrong conclusion from the right theorem. The mirrored mistake is to treat a memory promise as costless. Meeting a small ceiling usually means giving up retention, and every dropped structure is repeated work over the input. On an enormous read-only archive that trade is frequently worth making — but it is a trade, and it should be argued rather than assumed. ## What to write down A contract that survives review usually names both resources with different strengths: a **hard** memory ceiling, which is enforceable and falsifiable; and a latency statement whose strength matches what is actually known about the problem — a deadline where the complexity is known, a target with a defined degradation path where it is not. Saying which of the two is the guarantee and which is the target is the part that matters; a document that gives both the same weight has not made the decision at all.
- Is there any memory ceiling that does imply a useful time bound?Yes, at the bottom of the scale. A logarithmic work budget over a read-only input admits only polynomially many configurations, and a halting deterministic run visits each at most once, so the time bound is polynomial. Above that the implied bound is exponential in the space and stops being informative.
- What is the cost of meeting a tight memory ceiling on a huge input?Repeated work. Storage you give up becomes recomputation, typically extra passes over the input, which moves the cost straight into latency. The ceiling is therefore a design constraint rather than a tuning parameter, and its price shows up in the resource you did not promise.
- How should the latency side of such a contract be written when the problem is only known to fit in polynomial space?As a target with a defined degradation path, not a guarantee. Make the computation interruptible so a timeout yields a usable partial answer, state what that partial answer means, and reserve the word guarantee for the memory ceiling, which is the bound you can actually enforce.
- Treats a polynomial-space bound as reassurance about running time
- Says a memory ceiling implies nothing whatever about time
- Assumes a tight ceiling is free rather than paid for in extra passes
- Gives a deadline for work whose only proven time bound is exponential
- Claims the two bounds imply each other symmetrically