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).


You might be interested in the Universal Algebra point of view of Constraint Satisfaction Problems; see for example this survey by Libor Barto. One classical result in this area is Schaefer's dichotomy theorem.

  • $\begingroup$ Thank you for the pointer. That survey appeared in ACM SIGLOG News, I had taken a quick look at it but didn't remember seeing anything related to my question. However, now that I took a closer look, it does give a view of reductions which is of a similar flavor (the link is in the use of cartesian operads, or clones as they are called in universal algebra). I am glad to accept your answer here, but do you think there is hope that I get any more input by posting the question on TCS.SE? $\endgroup$ – Damiano Mazza Sep 27 '16 at 15:24
  • $\begingroup$ @DamianoMazza There's no harm in trying. $\endgroup$ – Yuval Filmus Sep 27 '16 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.