patternMinor
"Functorial" reductions?
Viewed 0 times
reductionsfunctorialstackoverflow
Problem
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 w
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 w
Solution
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.
Context
StackExchange Computer Science Q#63898, answer score: 2
Revisions (0)
No revisions yet.