Part A - Construct an algorithm

CMP.1 - Solve One Problem through Another or Transfer a Limit (Computational Reduction)

Type: Method Status: Usable, evolving Normativity: Normative

CMP.1:1 - Problem frame

Use this pattern when an unfamiliar computational problem might be solved through another problem, or when you need to determine what an assumed solver would make possible. The useful connection must turn admitted inputs into usable queries and recover the answer required by the original question.

Start by naming the problem to be answered and the problem whose solver will be used. Construct a conversion on one revealing input and say how each possible solver answer returns to the first problem. A working conversion, a failed return condition or a correctly directed impossibility consequence is a useful first result.

A computational reduction from A to B is an effective way to solve A using a solver for B. The main route constructs a query and an answer-recovery procedure; a later branch covers several queries. The reader needs elementary algorithms, finite representations, function composition and arguments about termination. The graph example explains its representation and assumes a suitable shortest-path solver. The undecidability example uses the stated halting result as a mathematical premise.

Use an available solver directly when its admitted inputs and answers already fit the question. C.29.2 supplies ordinary computational formulation. The present method develops the missing reduction and what follows from it. Approximate, randomized or physically realized computations require the corresponding answer and resource guarantees when they enter this connection.

CMP.1:2 - Problem

Two problems can have similar names or output shapes while admitting different inputs or requiring different guarantees. A conversion can lose the distinction that determines the answer, create a target input outside the solver’s domain, or leave no effective way to recover the original output.

A reduction can also be used backwards. Solving A through B supplies an A-solver when B is solvable; a known impossibility for A then constrains B. Reversing that implication can rule out a useful algorithm without justification.

The task is to construct the connection, establish its answer relation and effective execution, and carry only the consequence that its direction and resource conditions support.

CMP.1:3 - Forces

CMP.1:4 - Solution

Local mantra: specify both answers; construct the queries; recover every relevant answer; establish direction and cost; use the consequence; revise the changed condition.

CMP.1:4.1 - Specify the two problems and the intended conclusion

Call A the problem to be answered through B. State each problem’s admitted inputs and required outputs. An output might be a value, a satisfying witness, a decision including negative cases, or an approximation with a stated guarantee. Choose the forms actually needed.

For a decision problem, write A(x) for the proposition to be decided on input x. A solver must return a correct yes or no and terminate on every admitted input. If a proposed procedure only eventually confirms positive cases, retain that different capability in the problem statement.

For a witness problem, let Ans_A(x,y) mean that y is an acceptable answer for x. Specify what the procedure should do when no witness exists if that case is admitted. Use C.29.2 when the answer, representation or available elementary operations still need formulation.

Name the intended use of the reduction: build an algorithm from an available solver, transfer a known impossibility, or derive a resource consequence. This selects what effectiveness, return and cost arguments are needed.

CMP.1:4.2 - Construct a query without solving the original problem

Build a terminating procedure f that maps each admitted A-input x to an admitted B-input f(x). Work from the information actually present in x and the operations available to the conversion.

A useful way to begin is to identify what a B-instance must represent about x. Construct its components and relations, then retain any additional information needed for answer recovery. When the input contains a program, a conversion can assemble a new program description with that program embedded in it. Constructing the description and executing the embedded program are different operations.

Check the solver’s input conditions. A graph procedure accepting only nonnegative edge weights cannot be used unchanged when the conversion creates negative edges. A procedure specified for finite explicit inputs needs a suitable finite representation.

If producing f(x) already requires knowing A(x), the proposed conversion has not supplied the reduction. Replace that step with an effective construction from the available input, or retain it as the unresolved computational contribution.

CMP.1:4.3 - Construct answer recovery and establish correctness

For a single-query witness reduction, give a recovery procedure r(x,z). For every admitted x and every answer z the B-solver is permitted to return, establish:

Ans_B(f(x),z) implies Ans_A(x,r(x,z)).

The recovery must terminate under those conditions. Include negative outcomes, failure reports or approximation bounds when the A-contract needs them. A single fortunate B-answer is insufficient if the solver may validly return another answer that the recovery cannot use.

For a yes/no-preserving decision reduction, establish both directions:

A(x) iff B(f(x)).

Then the B-answer is the A-answer. If recovery reverses or otherwise changes the returned answer, state that rule and prove the resulting correspondence. For example, one positive implication alone leaves the no branch undecided.

When several queries are needed, construct the calling algorithm. State how a returned answer determines the next query and retained state, why every query is admitted, and why correct target answers lead to termination with the required A-answer. An adaptive reduction is a procedure using the solver, rather than one fixed input map.

Compose reductions by composing their actual conversions and recovery procedures. Intermediate answers must satisfy the next procedure’s conditions. MATH.17 and MATH.18 support the mathematical composition and interpretation questions; the present work additionally establishes effective execution under the selected computational model.

CMP.1:4.4 - Follow the direction of the consequence

For an established reduction from A to B:

• A suitable B-solver, together with the reduction, gives a suitable A-solver.
• If no such A-solver can exist under the stated model and guarantee, no B-solver with the assumed capability can exist.

Write the constructed A-procedure before using the second conclusion. It shows what the assumed B-solver would enable and where the contradiction arises.

Keep the scope of a limit. An impossibility for a total decision procedure on an unrestricted input class leaves other questions open: positive-case recognition, bounded execution, a restricted class, or a different computational model. Choose an alternative only when it supplies a useful answer for the work. The finite-state return in :5.2 shows such a change.

For a complexity consequence, use a reduction with the required resource bound. An unboundedly expensive input conversion supplies no efficient A-algorithm merely because B has one.

CMP.1:4.5 - Derive the cost that can change the choice

When cost matters, include input conversion, query size, solver calls and answer recovery under a named computational model. If conversion costs T_f(n), its output has size at most m(n), B costs T_B(m(n)), and recovery costs T_r(n,m(n)) including the returned answer size relevant to it, the one-query construction has the corresponding total bound:

T_A(n) <= T_f(n)+T_B(m(n))+T_r(n,m(n)).

If the answer size is not bounded through these arguments, include it explicitly. For several queries, sum the costs of their construction, calls and recovery, including any adaptive work between calls. Analyze peak simultaneous storage separately from total work.

The representation matters. A quantity written with n bits can have a value exponential in n; enumerating that many states changes the cost claim. Exact rational operations also have costs depending on operand length when bit complexity is the model.

Use the result to choose or reject the reduction for the current resources. Another solver, a smaller representation or a different computational construction can preserve the answer while changing cost. C.29.2 supplies the surrounding resource and accuracy formulation.

CMP.1:4.6 - Return a usable construction or a bounded limit

For solver reuse, return the input construction, solver conditions, recovery and relevant cost. A user should be able to follow an input through to its original answer.

For a limit, return the reduction argument, its computational assumptions and the excluded guarantee. Use that result to revise the actual question or allocation of work. A failed implementation attempt supplies neither this limit nor a reason to stop searching for a valid reduction.

When the input class, answer guarantee, representation or available solver changes, revisit the affected connection. Retain the earlier consequence for the conditions under which it was established.

CMP.1:5 - Archetypal Grounding

CMP.1:5.1 - Solve difference constraints through a graph problem

The input is a finite set of variables and inequalities of the form:

x_v <= x_u+w(u,v),

with rational weights. The required answer is an assignment satisfying all inequalities or a correct infeasibility report.

Construct a directed graph with one vertex per variable and an edge u to v of weight w(u,v) for each inequality. Add a new source s with a zero-weight edge to every variable vertex. Use a solver that permits negative edge weights and returns either shortest-path distances from s or a reachable negative cycle.

A negative cycle proves infeasibility: sum its inequalities. Every variable cancels, leaving 0 <= sum of cycle weights, which is false for a negative total.

If there is no negative cycle, all vertices are reachable from s and their shortest distances are finite. For every edge, the shortest-path condition gives:

d(v) <= d(u)+w(u,v).

Thus x_v=d(v) recovers a satisfying assignment. This proves the required return for either solver outcome.

For example, take x_b<=x_a+3, x_c<=x_b-2 and x_a<=x_c+1. Distances (d(a),d(b),d(c))=(-1,0,-2) satisfy all three. If the final bound changes to x_a<=x_c-2, the directed cycle has weight 3-2-2=-1 and proves infeasibility.

For n variables and m inequalities, construction adds n+1 vertices and m+n edges. Reading or assembling those lists and copying back an assignment takes O(n+m) operations under the explicit-graph model. Add the selected solver’s cost on that graph and the rational-arithmetic costs appropriate to the representation.

The graph is a computational construction for the given inequalities. If those inequalities describe schedules, flows or another subject, their physical or organizational adequacy is a further modeling question. The reduction has established the answer for the supplied mathematical constraints.

CMP.1:5.2 - An event decider would decide halting

A team asks for a procedure that always decides whether an arbitrary deterministic program with unbounded working memory will eventually emit a designated event. The input is a finite program description, its finite initial data and the event to be recognized. The guarantee includes terminating with “no” for a program that never emits it.

Use the halting problem as A: given a program P and input x, decide whether P(x) terminates. Under the ordinary Turing-computable model, no total algorithm decides this for all programs and inputs.

Construct a program Q with x and P’s description included. Q simulates P on x, suppresses the simulated program’s output, and emits the designated event if and when the simulation halts. The description of Q is obtained by placing the supplied data inside this fixed wrapper; constructing it does not run P(x).

If P(x) halts, Q emits. If P(x) does not halt, Q never reaches its emitting step. A supposed total event-decider applied to Q would therefore decide A in both cases. This contradicts the halting result, so the requested universal event-decider is unavailable under these assumptions.

The direction matters: halting was reduced to event decision. The argument constructed a halting decider from the assumed event decider.

Now change the admitted system to a fully represented deterministic finite-state machine with effective transitions and a decidable emitted-event label on each transition. Starting from its initial state, follow transitions while remembering visited states. Return yes upon the event; return no if the machine halts without it or repeats a state before emitting it. At most the number of reachable states can be visited before such repetition or termination. Determinism and complete state make the future repeat as well.

This supplies a usable decision procedure for the changed class. If an environment can add unrepresented inputs or the “state” omits a changing counter, restore those inputs or state before applying this finite-state result. C.29.2 and A.3.3.TR supply that formulation work. The original universal impossibility and this restricted procedure remain compatible.

CMP.1:5.3 - A small description can create an expensive search

An input describes b Boolean state variables. A conversion that explicitly constructs every possible state may produce 2^b vertices. Even a solver linear in the resulting graph size then gives an exponential dependence on b.

The construction may still be effective and useful for small b. For a larger budget-constrained use, keep the original answer condition and seek a representation or method that avoids explicit expansion, or derive a suitable restriction of reachable states. Calling the target solver efficient does not settle the cost of the whole reduction.

CMP.1:5.4 - Recover a witness through adaptive decision queries

The required answer is the lexicographically least satisfying assignment of a Boolean circuit C on n ordered input bits, or UNSAT. An available solver decides whether a supplied circuit has any satisfying assignment and terminates on either answer.

First query C. A negative answer gives UNSAT. After a positive answer, retain a prefix with a satisfying extension. Try its next bit as 0 and query the circuit with that prefix fixed. Keep 0 if the answer is yes; otherwise keep 1. The retained prefix still has a satisfying extension. After n bit choices it is a complete satisfying assignment; preferring 0 at each position makes it the least one.

For C(a,b,c)=(a or b) and (not a or c), the answers are:

C: yes -> prefix 0: yes -> prefix 00: no -> prefix 010: yes.

The recovered answer is 010. For circuit size N, copying each restricted circuit takes O(N) work. There are at most n+1 calls, giving total work bounded by (n+1)T_B(O(N))+O(nN+n) and sequential-call space O(N+n+S_B(O(N))).

If the solver only recognizes satisfiable inputs and may diverge otherwise, the query at prefix 00 can fail to return. This construction then lacks its required guarantee. Obtain a total decider or use finite enumeration, whose worst-case work is O(2^n N).

CMP.1:6 - Bias-Annotation

The solver’s familiar name can draw attention away from its admitted inputs and returned guarantees. Follow the actual conversion and recovery, including the negative branch the original problem requires.

An impossibility argument can also be overextended. Keep its input class, computational model and answer guarantee visible, then examine a changed useful question at those same points. A resource estimate is conditional on the representation used.

CMP.1:7 - Conformance Checklist

For the reduction being used:

• Both problems have stated admitted inputs and required answers.
• The conversion is effective from the supplied input and produces admitted queries.
• Every solver outcome relied on by the construction has an effective recovery with the required guarantee.
• The correctness argument covers the needed directions and termination conditions.
• The consequence follows the direction of the constructed solver reuse.
• A resource claim includes conversion, calls, recovery and relevant representation sizes.
• The result supplies an algorithm, a useful restricted alternative or a limit with a specific effect on the next move.

CMP.1:8 - Common Anti-Patterns and How to Avoid Them

Requiring the answer to construct the query. A wrapper program can be constructed without running the program it contains, as in :5.2. Identify that effective construction; treating a truth-dependent choice of wrapper as already computable would leave the original problem unsolved.

Using only the successful branch. Finding an emitted event confirms a positive case. The universal decision request also requires a terminating negative answer, which simulation alone leaves unresolved.

Reversing the reduction. Write the A-procedure using the B-solver before transferring an impossibility or an algorithm. Its actual calls determine the direction.

Hiding conversion cost behind the solver’s bound. Explicit expansion of b bits into 2^b states dominates the use in :5.3. Include the created instance and its storage in the resource argument.

CMP.1:9 - Consequences

An unfamiliar problem can acquire a usable algorithm through a constructed connection to another. The same form of reasoning can establish a limit by showing what an assumed solver would imply.

The reduction retains responsibility for inputs, answers and resource effects at the connection. A new solver or representation can improve it; a changed answer guarantee or input class can invalidate only part of its earlier use.

CMP.1:10 - Architectural Rationale

Effective conversion and answer recovery make reduction a computational method. Mathematical correspondence supplies the relevant implication, while computability and cost determine whether the connection can be used under the stated conditions.

Solver reuse and impossibility belong together because the latter follows by assuming and then constructing the former. Their guarantees and direction remain explicit. The shortest-path and program-wrapper cases demonstrate different uses of that shared method; neither application defines the scope of computational thinking.

C.29.2 already supplies the computational question, representation and ordinary progress account. This pattern develops a missing reduction, its answer relation and the consequence of an available or assumed solver. More specialized algorithm constructions can supply the conversion or the target solver.

CMP.1:11 - SoTA-Echoing

Erickson’s Undecidability notes, §§7.4-7.5 and 7.9-7.10, supplies a foundational account of effective program construction and the direction of reduction arguments. The adopted contribution is the explicit construction that turns an assumed solver into another solver. The event-wrapper example here uses the halting result under its stated computational model.

Erickson’s Shortest Paths supplies the directed-graph and negative-cycle machinery used in the solver-reuse case. The recovered inequalities and their infeasibility argument explain what that machinery answers in the source problem.

A direct algorithm is preferable when conversion adds effort without improving the needed result. When a reduction is useful, the choice among ordinary computability, bounded-resource, approximate or randomized reductions follows the answer guarantee being transferred. A preserved decision alone leaves an approximation ratio, probability or practical runtime to its corresponding argument.

CMP.1:12 - Relations

• C.29.2 specifies computational answers, representation, progress, accuracy and resources.
• C.29.1 establishes a subject correspondence when the computational problem describes something beyond the mathematical construction.
• MATH.17 and MATH.18 develop operations on operations, interpretations and their preserved consequences.
• MATH.4 and MATH.12 supply induction and constructive argument methods when the reduction needs them.
• A.3.3.TR recovers state and continuation distinctions, including those needed by finite-state restrictions.
• C.39 and C.40 help develop a missing computational way or explore alternatives when a construction remains unresolved.

CMP.1:End

CMP.2 - Derive a Recursive Procedure from a Problem Decomposition

Type: Method Status: Usable, evolving Normativity: Normative

CMP.2:1 - Problem frame

Use this when you can state the answer required from a finite input, but a procedure for obtaining it is missing or unaffordable. Parts of the task resemble the whole, or a transformation produces another instance whose answer could help. You need to choose those subproblems and determine what they must return.

An engineer, researcher or AI agent may recognize a recursive formula yet be unable to turn an unfamiliar problem into one. A common difficulty appears at recombination: each part returns a correct answer to its own question, but those answers omit information needed for the whole. Another appears at progress: a call changes its input without bringing computation closer to a return.

The gain is a recursive procedure with usable base cases, a reason its calls return, a justified way of combining their results and an initial account of its cost. The reader needs to follow finite case distinctions, functions and a simple inductive argument. MATH.4 can supply that argument; C.29.2 supplies the relation between a computational answer and the question it is meant to settle.

Use a suitable existing procedure directly when it already answers the question within the available resources. This method develops recursion for obtaining a finite answer. A server, stream or other intentionally continuing process needs a progress condition appropriate to that behavior.

CMP.2:2 - Problem

How can one discover a recursive algorithm whose subproblems are obtainable, whose answers suffice to reconstruct the requested result, and whose unfolding has an acceptable cost?

Choosing a familiar equation or writing a self-call does not settle those questions. The designer must connect the meaning of a subproblem to the operation that uses its answer.

CMP.2:3 - Forces

CMP.2:4 - Solution

State the answer → propose smaller questions → derive the join → strengthen what must be returned → establish return → compare the work.

CMP.2:4.1 - Fix the question and the available operations

Describe an input x, the information available about it, and what a returned answer must allow its recipient to do. Asking for an optimum value, one attaining object, or every attaining object gives different result requirements. State the empty and degenerate cases when they belong to the input family.

List the operations that can actually be performed on this input: inspect a constructor, split an interval, compare keys, compute a remainder, test a condition, or call a supplied procedure. A proposed step such as “choose the correct partition” remains a construction task until the partition can be obtained.

For example, maximum segment sum on a sequence of integers asks for a contiguous nonempty segment with largest sum. Returning its sum answers a value query; locating the segment also requires endpoints. Permitting the empty segment changes the base case and the answer on an all-negative input.

CMP.2:4.2 - Choose a decomposition by asking how answers would join

Take a representative input and suppose that selected smaller questions have been answered correctly. Try to construct the answer for this input from those returned values. This local design question avoids having to unfold the entire recursion while inventing it.

Useful proposals include removing one element, splitting into balanced parts, following the constructors of a structured input, or transforming the input while decreasing another measure. The last case includes Euclid’s replacement of a pair by a divisor and remainder. Input size need not decrease in every component.

For each proposal, account for every form a valid answer can take. If a sequence is split into left and right parts, an optimal contiguous segment lies wholly on one side or crosses the boundary. The crossing case shows what the two recursive answers must supply.

Keep the proposal that makes the join both justified and obtainable. If the only available join searches the original problem again, change the subproblem question, retain more information, or try another decomposition.

CMP.2:4.3 - Strengthen the returned result when the join needs more

Write the join using named values. Each value must come from the input, a smaller answer or an available local operation. A missing value identifies a specific revision of the subproblem, rather than a reason to discard recursion as a whole.

For maximum segment sum, the best segment on each side is insufficient: a crossing segment uses a suffix of the left side and a prefix of the right. Let each nonempty part return four quantities:

• T: the sum of the whole part;
• P: the largest sum of a nonempty prefix;
• S: the largest sum of a nonempty suffix;
• B: the largest sum of a nonempty contiguous segment.

For a left summary L and right summary R, construct:

T = L.T + R.T
P = max(L.P, L.T + R.P)
S = max(R.S, R.T + L.S)
B = max(L.B, R.B, L.S + R.P)

The alternatives in each maximum come from the possible locations of the corresponding segment. To return an actual segment, carry the endpoints attaining each selected prefix, suffix and best segment. Choose a consistent rule for ties when only one witness is wanted.

This is the algorithmic use of strengthening an inductive result in MATH.4. The additional design decision is what summary enables an affordable join for the chosen problem decomposition. Further questions may require a different summary.

CMP.2:4.4 - Supply base cases and a decreasing measure

Give a direct result for each case on which recursion stops. Then show that every recursive call reaches such a case after finitely many steps. A nonnegative integer that strictly decreases is often enough. A finite input constructor or a well-founded ordering can supply the same argument when one numerical size is awkward.

For the segment procedure, a singleton v returns (v,v,v,v). Split every longer interval into two nonempty shorter intervals. Its length decreases along every call path. This also explains why an empty interval needs its own convention or must be excluded before calling the procedure.

For nonnegative integers with b>0, Euclid’s call (a,b) → (b,a mod b) decreases the second component because 0≤a mod b<b. The first component may increase relative to its old value; it is the selected measure that must decrease. At b=0, return a, with the intended convention for (0,0) fixed separately.

When a termination checker fails, inspect which decrease is absent from its account. A supplied difference, lexicographic measure or invariant may express the progress already present in the procedure. If progress is genuinely missing, repair the procedure or weaken its claimed result. A small successful run alone does not establish return on every allowed input.

CMP.2:4.5 - Establish the result and expose its computational cost

Use the base and smaller-call assumptions to establish the returned property. Recombination must work for every smaller answer allowed by its specification, including the selected tie behavior. When deriving a program from an existing proof, MATH.12 recovers the operations hidden in that proof.

Count the subcalls and local work. A recurrence for mathematical values and a recurrence for computational cost answer different questions. For balanced segment splitting with interval views, constant-cost arithmetic and the four-value join, the work satisfies W(n)=W(floor(n/2))+W(ceil(n/2))+O(1), giving O(n) operations. Sequential depth-first evaluation retains O(log n) summaries on its call stack. Copying each subarray instead adds work at each level; growing integer values also change the cost per addition.

If equal subproblems recur, CMP.3 can identify and share them. If the decomposition generates alternatives that can be ruled out, CMP.4 can construct those exclusions. If representation dominates the cost, compare the access and update operations before replacing the mathematical construction.

CMP.2:4.6 - Use the result and revisit the assumption that changed

Run a small case through the complete procedure, including the use of its returned answer. Change one condition that stresses the construction: empty input, a boundary case, a different output request or a resource limit. Follow the affected base, join and progress arguments.

The result may be a working procedure, an unaffordable but informative construction, or a located missing operation. Use that difference to choose the next algorithmic move. Formal proof or additional testing is chosen for the uncertainty that matters to the receiving use.

CMP.2:5 - Archetypal Grounding

CMP.2:5.1 - A join that initially loses the answer

For [-2,3,-1,4,-5], split into [-2,3,-1] and [4,-5]. Their best sums are 3 and 4. Keeping only those values would miss the crossing segment [3,-1,4], whose sum is 6.

The strengthened summaries are L=(0,1,2,3) and R=(-1,4,-1,4), ordered as (T,P,S,B). The join yields (-1,4,1,6). With attaining endpoints retained, it returns the segment from the second through fourth element. The user can now obtain the segment rather than merely knowing its value.

Changed condition: suppose the wanted segment may contain at most two elements. The former crossing winner has length three. The four maxima have discarded the sums of shorter candidate suffixes and prefixes. Add prefix and suffix results indexed by permitted length, combine only lengths whose sum is at most two, and keep the same restriction on internal best segments. In this case the answer becomes 4, attained by [4]. For a general limit k, a straightforward join over length pairs costs O(k²); the resource consequence can justify a different algorithm. Reusing the old four-value join would silently answer the earlier question.

CMP.2:5.2 - A subproblem obtained by a transformation

To compute gcd(48,18), replace the pair by (18,12), then (12,6), then (6,0), and return 6. The equality gcd(a,b)=gcd(b,a mod b) follows because a common divisor of either pair divides both entries of the other pair. The remainder operation and decreasing second component turn that equality into a returning procedure.

If the next use also needs coefficients u,v with u*a+v*b=gcd(a,b), the returned number alone is insufficient. Suppose the smaller call supplies d=u'*b+v'*r, with r=a-q*b. Substitution gives d=v'*a+(u'-q*v')*b; return the updated coefficients too. For the original pair, 6=(-1)*48+3*18. The same recursive decomposition supports a stronger output through a changed join.

CMP.2:6 - Bias-Annotation

Familiar syntax can make one decomposition appear inevitable. Compare its join and cost with another plausible decomposition when those differences can change the choice. Conversely, an elegant asymptotic bound can hide operations that the actual representation makes expensive.

A successful example demonstrates the construction and can expose a missing case. The general result depends on the base, joining and progress arguments, with any additional assurance selected for the actual use.

CMP.2:7 - Conformance Checklist

• The input and wanted result distinguish a value from any witness or continuation information that is needed.
• Each subproblem is constructible from available data, and its returned specification supplies the join.
• The base cases cover the stopping situations; every recursive path has the stated progress toward one of them.
• The join preserves the answer property, including boundaries and the chosen treatment of ties.
• The cost account includes branching, recombination and representation costs material to the decision.
• A changed requirement is followed through the returned information and affected clauses before the procedure is reused.

CMP.2:8 - Common Anti-Patterns and How to Avoid Them

CMP.2:9 - Consequences

The method makes recursive algorithm design available as a sequence of inspectable choices. It exposes a useful link between mathematical construction and algorithmics: strengthening what a subproblem returns can make a previously unavailable or costly computation possible.

The resulting algorithm need not be the fastest one. Its explicit subproblem and join create opportunities for sharing, new representations, parallel execution or replacement by another algorithm. Those improvements retain their own correctness and resource questions.

CMP.2:10 - Architectural Rationale

Subproblem meaning, recombination, progress and cost belong together because changing one can force a change in the others. Starting from a recursive syntax would obscure the discovery of the required question and summary. Starting from an induction proof alone can leave the effective decomposition and cost unresolved.

MATH.4 supplies witness construction by induction; MATH.12 supplies extraction from a proof. This pattern constructs and compares recursive obtaining procedures, including decompositions that do not follow the input’s constructors. CMP.3 changes how repeated calls are evaluated without silently changing what they ask. C.29.2 retains the common computational formulation and its connection to the receiving question.

CMP.2:11 - SoTA-Echoing

Erickson, Algorithms, chapter 1 develops recursion through reductions to simpler instances and separate correctness and running-time arguments. This remains a useful foundational construction line. Adopt the local design question about a correct smaller answer; adapt it by making the information required at the join explicit and testing a changed output request. A remembered recurrence alone supplies less help when the decomposition itself is missing.

For the construction in :4.2–4.5, an available recurrence or input-structural split is the simpler alternative when it already returns enough information for the join and meets the cost requirement. Strengthening a subanswer is worth its extra work when that simpler return loses the requested result, as the four-value segment construction and coefficient-returning divisor procedure demonstrate. Reconsider this choice when a different output, representation or competing decomposition changes either sufficiency or total cost.

The current Lean reference on recursive definitions distinguishes structural recursion, well-founded measures and forms of partial or continuing behavior. Adopt the distinction between a missing syntactic decrease and an absent termination argument. Formal encoding can check a consequential or difficult construction; its additional work is unnecessary for simply exploring a decomposition. No particular proof assistant or finite-return account is imposed on every computational process.

CMP.2:12 - Relations

• C.29.2 - Computational Formulation: supplies the requested computational result, elementary operations and connection to use.
• CMP.1: supplies reuse through an effective reduction; recursion constructs the repeated same-family reduction and its return.
• MATH.4 and MATH.12: supply inductive construction and the obtaining operations recoverable from proof.
• CMP.3: shares repeated calls and chooses their evaluation and storage; CMP.4 handles exclusions among alternative extensions.
• MATH.20: supplies bounds used when comparing cost or consequences. The general resource and portfolio methods choose among the constructed alternatives.

CMP.2:End

CMP.3 - Share and Schedule Repeated Subcomputations

Type: Method Status: Usable, evolving Normativity: Normative

CMP.3:1 - Problem frame

Use this when a procedure repeatedly obtains the same intermediate answer, or retains so many intermediate values that it cannot finish within the available memory. You need to determine which work can be shared, when to perform it, and what to retain for later use.

The situation occurs in dynamic programming, symbolic evaluation, database computations, program analysis and differentiation of computational graphs. The repeated unit is a subcomputation with stated inputs and a needed result. Similar-looking calls may still require different answers because their data, assumptions or effects differ.

The gain is an evaluation procedure that performs less repeated work or fits the available storage while preserving the requested answer. The reader needs to understand a function call and a directed dependency graph; the graph is explained here as a set of intermediate results with arrows from each prerequisite to its consumer. CMP.2 can supply the original recursive procedure.

Direct recomputation is often best for a cheap, seldom-repeated operation. Apply this method when sharing or storage choices can change the feasibility or cost of the computation. A changing environment requires the meaning of reuse to be established before previous results are used.

CMP.3:2 - Problem

How can repeated computations be identified and reorganized without merging cases that need different answers, using an evaluation order and storage policy that support the requested result?

“Cache the answer” leaves three questions open: what counts as the same question, which answers must already be available, and whether the retained information suffices for the eventual output.

CMP.3:3 - Forces

CMP.3:4 - Solution

Name the repeated question → retain its determining information → expose dependencies → choose evaluation order → choose retained values → recover the required output.

CMP.3:4.1 - State what a subcomputation means

Describe the result of one subcomputation as a function of its inputs and fixed environment. Include every condition that can change the returned answer or its use. A pair of sequence indices identifies an edit-distance subproblem only within specified sequences, edit operations and costs.

For optimization, distinguish the best remaining value from accumulated cost already incurred. If two histories lead to the same remaining problem but have different past costs, share the remaining answer and combine it with each history’s cost. Merging the complete histories may lose a better total. When history changes the allowed future choices, retain that history information in the state.

This question is also useful before an implementation exists: identify the small family of questions that many possible constructions would ask. A recursion tree can then be designed around those questions instead of optimized after the fact.

CMP.3:4.2 - Define reuse by the answer the continuation needs

Choose a representation of subproblem identity, often called a key. Equal keys must imply interchangeable answers for the intended continuation. The key can contain input values, an immutable object’s identity, a data revision, parameters and relevant assumptions. A cache local to one fixed computation may keep some of these implicit in its scope.

MATH.2 supplies the reasoning behind an identification: the operation used after identification must give the same required result whichever representative was used. An implementation also needs an effective way to recognize the keys. A hash narrows candidates; resolve collisions before treating different data as identical.

Distinguish completed answers from computations that have merely begun. Reading an unfinished entry as a result can introduce circular reasoning. In parallel evaluation, decide whether repeated demand waits for one producer or safely computes another copy; preserve the meaning of completion in either case.

For an operation with effects, state what reuse preserves. Replacing two reads of a changing sensor by one stored reading changes the observation sequence. Repeating a random draw and reusing one sample changes dependence. Sharing a pure calculation on an already obtained reading or sample can be valid. Select the intended operation before choosing the reuse rule.

CMP.3:4.3 - Construct the dependency graph and an evaluation order

For each distinct subproblem, identify which other results are needed to obtain its answer. Draw an arrow from a prerequisite to its consumer. Count distinct states and the work needed to combine each state’s prerequisites and alternatives; the number of states alone does not establish the total cost.

If dependencies are acyclic, two standard constructions are available:

These methods can be combined by regions. Independent ready states can also be evaluated concurrently, provided the sharing and combination operations preserve the result.

A directed cycle prevents this simple ordering. Determine whether it is an erroneous recursive dependency, a finite-horizon problem missing its horizon coordinate, or a genuine fixed-point problem. For a genuine cycle, provide the iteration, ordering or other solving method and its result conditions. Adding memoization alone does not solve mutually dependent equations.

CMP.3:4.4 - Retain what remains live, and recompute selectively

A value is live while a later operation will need it and cannot obtain it more cheaply by another means. Find its last planned consumer. After that use, the storage can be reused unless the requested final output needs the value for reconstruction.

Compare full retention, a moving set of recent values, and selected stored checkpoints from which intervening work is recomputed. Include key storage, lookup, copying, arithmetic size and transfer costs when they can change the choice. The mathematical dependency graph can be unchanged while these execution costs differ substantially.

Recomputation must reproduce the needed value from retained inputs and conditions. If it repeats an external effect or uses changed data, its meaning needs separate treatment. A stored checkpoint is useful only if it contains enough information to restart that part of the computation.

CMP.3:4.5 - Recover the value, witness or continuation actually requested

For each return, ask what the recipient must obtain. A dynamic program may return only an optimum value, one attaining sequence of choices, a count, or all attaining sequences. Store a selected predecessor when one witness is required, retain all relevant alternatives when their multiplicity matters, or provide an additional reconstruction procedure.

A small table is not automatically a complete answer. Sometimes an extra pass or a recursive split reconstructs a witness using less storage than retaining all predecessors. Include that work in the cost comparison.

When inputs or requirements change, identify the affected dependencies. Invalidate or recompute their consumers, or show that the changed information cannot alter those results. Choose the simplest reuse boundary that pays for itself; rebuilding a small calculation can be cheaper than maintaining fine-grained dependencies.

CMP.3:4.6 - Compare the resulting procedure with the original

Evaluate one complete use under both procedures and follow a changed condition that can break the proposed identification or storage policy. Check returned content as well as operation counts. The method’s result is the changed computation and its resource consequence.

Use C.11.DUA when deciding whether another measurement, argument or experiment would change the choice. A theoretical bound can guide an initial implementation; actual resource observations can select among alternatives whose constant factors or memory behavior matter.

CMP.3:5 - Archetypal Grounding

CMP.3:5.1 - Obtain a sequence-editing answer without expanding repeated calls

Let D(i,j) be the smallest number of unit-cost insertions, deletions and substitutions transforming the first i characters of fixed sequence A into the first j characters of fixed sequence B. Matching characters cost zero. Then:

D(0,j) = j
D(i,0) = i
D(i,j) = min(D(i-1,j)+1,
             D(i,j-1)+1,
             D(i-1,j-1) + (0 if A[i]=B[j] else 1))

Here character positions start at 1. Each alternative identifies the last edit or match. Removing it leaves the corresponding smaller problem; adding it to a best smaller answer supplies a candidate for the whole prefix. Thus the minimum covers the possible last steps.

Naively unfolding this recurrence repeatedly requests the same prefix pairs. Within one fixed pair of sequences and one cost rule, use (i,j) as the key. Dependencies have smaller i+j, so increasing rows and then columns gives a valid order.

For A=CAB and B=AB, the complete table is:

The result is 1; deleting the initial C attains it. There are (m+1)(n+1) states for lengths m,n, with constant work per interior state under constant-cost character comparison and small-integer arithmetic. Full retention uses O(mn) cells. If only the distance is required, the preceding and current row suffice, giving O(n) working cells.

Changed output: the recipient now needs an edit script. The final distance and two surviving rows do not supply the deleted path. One repair stores a minimizing predecessor for each cell and traces back from (m,n). Another computes forward and backward costs to a middle row, chooses a column minimizing their sum, and recursively reconstructs the two halves. Every edit path crosses that row, which justifies the split. This second construction exchanges recomputation for storage; CMP.2 supplies the recursive decomposition. Neither choice alters the meaning of an allowed edit.

Changed reuse scope: for A=CB, B=AB, the value at (2,2) is 1; for A=CA, B=AB, it is 2. A global cache keyed only by (i,j) would conflate them. Restrict the cache to a fixed input pair or include the input identity and relevant conditions.

CMP.3:5.2 - Share an expression while preserving its interpretation

For f(x,y)=(x+y)*(x+y)+(x+y), build one node t=x+y with three uses, then obtain t*t+t. With x=2,y=3, the result is 30. This replaces three additions of x+y by one and shares its stored value until the final addition.

If y changes to 4, t and its consumers must change; the result becomes 42. If each occurrence instead meant “read the next measurement and add x,” the shared expression would change the computation’s meaning. The subproblem must be a fixed pure addition of supplied values for this identification to hold.

In differentiation of a longer expression graph, intermediate values may be needed again in reverse order. Keeping all of them can exceed memory. Retain selected restart values and recompute intervening pure operations when needed, comparing the extra work with reduced storage. This applies the same method to a different receiving algorithm.

CMP.3:6 - Bias-Annotation

Visible repetition can encourage indiscriminate caching. The profitable unit may instead be a larger common subproblem, or no shared unit at all when lookup costs dominate. A small count of stored cells can also hide large objects, metadata and movement between memory levels.

Results obtained from fixed data invite overgeneralization to changing environments. State where a key’s omitted parameters are held fixed, and revisit that boundary when the result is reused elsewhere.

CMP.3:7 - Conformance Checklist

• The repeated question and its determining data are recoverable from the key and its stated scope.
• Equal keys justify the required reuse, including relevant effects, randomness and changed inputs.
• Dependencies determine an evaluation order, or a separate method resolves the genuine cycles.
• Completed results are distinguished from work still being evaluated.
• Storage and recomputation choices preserve the final value, witness or continuation that is required.
• The resource comparison counts relevant transitions, arithmetic, access and storage as well as states.
• The changed-condition use follows the dependency or output requirement that actually changed.

CMP.3:8 - Common Anti-Patterns and How to Avoid Them

CMP.3:9 - Consequences

Many repeated call trees become a much smaller graph of distinct questions. Evaluation order and retention become design choices, making time, memory and output reconstruction comparable.

The transformation creates responsibilities for identity and change. Its benefit depends on repetition, graph size and access costs; a dependency graph can itself be enormous. A correct shared computation can still be unaffordable, which may call for a changed representation, approximation or problem formulation.

CMP.3:10 - Architectural Rationale

Identity, dependencies, evaluation and lifetime form one method because changing the result being shared can alter all four. Separating “add a cache” from the required continuation would hide the main correctness question. Including selective recomputation prevents storage minimization and computation minimization from being treated as the same objective.

The mathematical identification is supplied by MATH.2, the subproblem construction by CMP.2, and common computational formulation by C.29.2. This pattern supplies the algorithmic reorganization. It can serve numerical, symbolic and learning procedures.

CMP.3:11 - SoTA-Echoing

Erickson, Algorithms, chapter 3 develops memoization, deliberate evaluation order, space saving and reconstruction of sequence-editing answers. Adopt the progression from a meaningful recurrence to distinct subproblems and their evaluation. Extend the identity question explicitly to changing inputs and effectful operations. The CAB example is a small independent derivation of that general design approach.

Hirschberg’s linear-space reconstruction is a historical but still useful counterexample to the assumption that reconstructing a sequence requires retaining a complete table. Its middle-split method also applies to edit paths. Adopt reconstruction as a choice between storage and additional calculation; do not claim its cost is optimal for every input representation or modern machine.

Current JAX checkpointing documentation shows the same storage/recomputation choice in automatic differentiation. Adopt its substantive distinction between saved intermediates and recomputed pure operations. Compiler behavior and hardware costs affect the best schedule; a particular library interface is an example of realization rather than a prerequisite of this method.

The working choice in :4.3–4.5 is between retaining all needed intermediate answers, recomputing them when requested, and retaining selected answers from which others can be reconstructed. Full retention is simpler when memory is ample and reconstruction would dominate. Recalculation avoids maintaining entries whose results are cheap or rarely reused. Selective retention pays extra scheduling or reconstruction work when it preserves the required answer under a tighter memory limit; the edit-script construction supplies one such choice. Reconsider it when effects change which calls can be shared, the recipient needs a different witness, readout costs change, or a competing reconstruction method improves the same resource trade-off.

CMP.3:12 - Relations

• CMP.2: constructs the subproblems and their combination; this method changes how repeated questions are evaluated.
• MATH.2: supplies identification under operations; A.3.3 helps restore state information when equal retained states allow different continuations.
• C.29.2: supplies computational result and resource conditions. C.29.3 applies when realization changes the relevant execution assumptions.
• MMP.8: supplies information restrictions for adaptive choices; a computation used to obtain such a policy must preserve the observations and history on which its choices depend.
• C.11.DUA: selects additional checking or measurement for a decision that could change, including the value of further optimization.

CMP.3:End

CMP.4 - Construct Computational Search with Justified Exclusions

Type: Method Status: Usable, evolving Normativity: Normative

CMP.4:1 - Problem frame

Use this when an answer must be constructed by choosing among alternatives, direct enumeration is too costly, and information about a partial choice can eliminate some of its completions. You need a search procedure that saves work while retaining the answers its recipient needs.

Examples include finding an assignment satisfying constraints, selecting a best combination, constructing a counterexample and exploring possible program states. The general difficulty is deciding which alternatives may be omitted. A promising search order can find an answer quickly while providing no reason to exclude the alternatives visited later.

The gain is a search with explicit coverage, useful exclusion rules and a result that remains interpretable if computation is interrupted. The reader needs finite sets, logical conditions and inequalities; MATH.20 supplies a more developed bound argument. C.29.2 supplies the wanted computational answer.

Use direct construction or enumeration when it already solves the problem at acceptable cost. Heuristic search is also useful when a good candidate is enough. Apply the exclusion method to the conclusions that must be retained, without requiring proof of global optimality for every candidate search.

CMP.4:2 - Problem

How can a procedure omit whole sets of candidates and still return a valid witness, a justified optimum or a warranted statement that no required answer exists?

The exclusion must concern every relevant completion represented by the omitted branch. Failure of one attempted completion or poor predicted performance alone does not establish that result.

CMP.4:3 - Forces