# “Functorial” reductions?

If I understand correctly, $\mathsf{NC}^0$ reductions are taken as the formalization of the concept of "local" reduction, i.e., a reduction that acts locally on substructures of the instances of the problem to be reduced: they map fixed-size "gadgets" of the source problem to fixed-size structures of the target problem. It is my (hopefully correct) understanding that this kind of reductions occur ubiquitously in structural complexity theory.

An example: to reduce CIRCUIT VALUE to MONOTONE CIRCUIT VALUE (or MCV), one applies the following local transformations, which "double" every gate and every input (see e.g. Cook and Nguyen's Logical Foundations of Proof Complexity, proof of Theorem VIII.1.7, or slide 6 of this): \begin{align*} a &\mapsto (a_+,a_-) \\ 0 &\mapsto (0,1) \\ 1 &\mapsto (1,0) \\ \lor(a,b) &\mapsto (\lor(a_+,b_+),\land(a_-,b_-)) \\ \land(a,b) &\mapsto (\land(a_+,b_+),\lor(a_-,b_-)) \\ \lnot(a) &\mapsto (\land(a_-,a_-),\land(a_+,a_+)) \end{align*} After applying this transformation, we obtain a monotone circuit with $2$ outputs, call them $o_+$ and $o_-$, such that the value of the output $o_+$ is exactly the value of the original circuit ($o_-$ is its negation). To obtain an instance of MCV (a circuit with only one output), one simply projects on $o_+$, which means plugging a constant (i.e., independent of the original circuit) $2$-input, $1$-output circuit to the outputs of the circuit obtained above.

The whole operation is obviously in $\mathsf{NC}^0$, because bounded-depth circuits can not only implement the local transformation above (taking gadgets to substructures) but can also add arbitrary "constant" substructures (in this case, circuits), where "constant" means depending only on the size of the source instance.

I am interested in reductions which are, so to speak, "purely functorial", in the sense that they map gadgets to substructures but are not allowed to add any "constant". In the above example, the first part of the reduction would be functorial, whereas projecting on the $o_+$ output breaks functoriality. My question is:

Have "functorial" reductions ever been considered and, if so, under what name and for what purpose?

(The term "functorial" comes from the identity $F(f\circ g)=F(f)\circ F(g)$ which is at the basis of the definition of functor. If one sees problem instances as freely built out of basic gadgets, then functoriality means exactly "gadget to substructure". One could also say "homomorphic". Another analogy may be made with linear algebra: functorial reductions would be linear maps wheras $\mathsf{NC}^0$ reductions are affine maps).

I am pretty sure that "functorial" reductions are too restrictive to be of general interest. For instance, I do not see how CIRCUIT VALUE could be $\mathsf P$-complete under such reductions. However, the variant of CIRCUIT VALUE in which one asks for the value of a specified output out of possibly many, would still be $\mathsf P$-complete (this "multi-output" variant is of course equivalent to CIRCUIT VALUE under $\mathsf{NC}^0$-reductions), as well as the similar variant of MCV. So the notion is not completely void of significance. Also note that "functorial" reductions are incomparable w.r.t. projections: they are more general in one sense (the local dependence is not necessarily "bitwise") but more restrictive in another (projections are still allowed to add arbitrary substructures, i.e., break functoriality).