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.