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.