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.