  We are interested in the following validation problem for computational
reductions: for algorithmic problems $P$ and $P^\star$, is a given candidate
reduction indeed a reduction from $P$ to $P^\star$? Unsurprisingly, this
problem is undecidable even for very restricted classes of reductions. This
leads to the question: Is there a natural, expressive class of reductions for
which the validation problem can be attacked algorithmically? We answer this
question positively by introducing an easy-to-use graphical specification
mechanism for computational reductions, called cookbook reductions. We show
that cookbook reductions are sufficiently expressive to cover many classical
graph reductions and expressive enough so that SAT remains NP-complete (in the
presence of a linear order). Surprisingly, the validation problem is decidable
for natural and expressive subclasses of cookbook reductions.
