CMP.11:4 - Solution
Fix access and answer → construct indistinguishable alternatives → bound how fast observations separate them → respect the cost and error quantifiers → state the limit → change the assumption that constrains the work.
CMP.11:4.1 - State the computational model and the claimed quantity
Specify the admitted inputs, promised structure, allowed queries or operations, prior information and required output. Count what the claim concerns: number of input probes, comparisons, transmitted bits, retained states, total time or another defined resource.
Include preprocessing and advice where they depend on the input. If preprocessing builds an index, distinguish its cost from a subsequent query’s cost. An operation that reveals an entire vector is different from one that reads one bit, even if both are written as one function call.
State whether the bound concerns worst-case or expected cost, deterministic or randomized computation, and exact or error-tolerant answers. For randomization, say whether the error guarantee holds on every input and which randomness is available. These quantifiers determine the argument.
CMP.11:4.2 - Construct alternatives that the available observations have not separated
Describe a transcript: the sequence of queries and replies, or messages and observations, available to the procedure. Consider all inputs still consistent with it. If two of those inputs require incompatible answers, a deterministic procedure seeing that transcript cannot correctly finish on both.
Construct those alternatives rather than simply counting unknown data. For a bit query, place a decisive difference at an unread position. For a comparison algorithm, retain different orders compatible with the observed comparisons. For a communication or streaming algorithm, find different earlier inputs that lead to the same message or stored state but require different outputs after one common continuation.
Adapt the construction to the permitted answer. Distinct inputs do not need separate transcripts when the same answer is acceptable for both. A common approximation interval or permitted error can therefore weaken the lower bound.
CMP.11:4.3 - Turn indistinguishability into a resource bound
Use the form that fits the access:
- Adversary: answer queries while retaining incompatible possible inputs. Show how many queries are needed before no such pair remains.
- Counting: if each observation has at most b possible replies, q observations have at most
b^qtranscripts. If N input classes require mutually different outputs, thenb^q≥N, givingq≥log_b Nfor a worst-case depth bound. - State or message collision: with fewer than N distinguishable retained states or messages, two of N necessary input classes collide. A shared continuation then forces an error.
Establish that each constructed transcript is consistent with at least one admitted input. An adversary that combines incompatible answers proves nothing about the actual problem. A counting argument needs output-distinct classes, not merely many syntactically different inputs.
When an algorithm already provides an upper bound in the same model, compare the two. Matching orders of growth can establish asymptotic optimality for that model. A gap locates remaining room for a better construction or a stronger argument; it is not itself proof that the current algorithm is improvable.
CMP.11:4.4 - Handle randomization and average cost with their own argument
Fixing random choices gives a deterministic procedure, but its hard input may depend on those choices. That alone does not establish a bounded-error randomized lower bound on a fixed input.
One route chooses a distribution on inputs before the random choices. If every deterministic procedure within the allowed budget has error greater than δ under that distribution, averaging gives the same obstruction for any mixture of them. A randomized algorithm with error at most δ on every input would contradict it. Use the matching cost convention; a worst-case budget argument does not automatically establish a claim about expected budgets.
Another route couples runs on two inputs using the same random choices and bounds how often they see different observations. Section :5.1 applies this directly. A statistical or information inequality can supply a broader version when observation distributions overlap instead of agreeing exactly.
Keep quantum queries or stronger observation primitives outside a classical-query conclusion unless the proof actually covers them. Their admissibility is a model choice, not an implementation detail that can be ignored.
CMP.11:4.5 - Return the limit with a useful continuation
State the bound, input family, access, error and cost conditions together. Indicate whether it rules out the requested budget, establishes optimality within an order, or leaves a gap.
Identify a consequential escape: restrict the input by a defensible promise, allow a weaker answer or error probability, acquire an additional observation, preprocess and retain information, use a stronger primitive, or change the representation. Determine which premise of the lower-bound argument that change removes, then construct the new procedure. Renaming the same operations does not escape the bound.
Use C.11.DUA to decide whether proving a tighter bound or obtaining additional information would change the next move. A sufficient lower bound can already justify changing the task; there is no obligation to solve a harder open complexity question first.