What does $\mathsf{AC^0}$ many-one reduction mean?
I know about polynomial time reductions, but I'm not familiar with $\mathsf{AC^0}$ reductions.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time many-one reduction, except that instead of requiring that the mapping takes polynomial time, we require that the mapping is in AC0.
David Richerby further explains: "AC0 is a very low-complexity class so it can be used, for example, to study reductions between logspace problems, which doesn't make sense with polytime reductions since, then, the reduction would be more powerful than the problem class being studied." For instance, if problems A,B can be reduced to each other with polynomial-time reductions, then you learn that their complexity can't be exponentially different (if one is polynomial, the other must be too), but it's possible that they still might be fairly different (polynomially different). If they can be reduced to each other with AC0 reductions, then this has stronger implications about their complexity (it has to be pretty similar).
-
2$\begingroup$ It's probably also worth mentioning that AC0 many one reduction is normally understood to mean Dlogtime-uniform AC0 reduction, because of its equivalence to reductions by formulas in first-order logic. There are cases where one falls back to P-uniform or non-uniform AC0, if this makes it possible to prove some interesting theorem(s), like described here. $\endgroup$ Jun 8, 2018 at 21:05
-
$\begingroup$ @ThomasKlimpel, fascinating! You exceeded my knowledge. Would you care to write an answer explaining that? I didn't know about that. $\endgroup$– D.W. ♦Jun 8, 2018 at 21:21
$\begingroup$
$\endgroup$
4
The "what is" part of the question was succinctly answered by D.W.:
An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit. It's just like a polynomial-time many-one reduction, except that instead of requiring that the mapping takes polynomial time, we require that the mapping is in AC0.
I mentioned (in a comment) that AC0 many one reduction is normally understood to mean Dlogtime-uniform AC0 reduction. This implies that AC0 reductions are provably weaker than log-space reductions (and polynomial time reductions).
This is important for answering the implicit "why do we care about AC0" part of the question. Many complete problems stay complete under extremely weak notions of reduction, like Dlogtime many-one reductions (or even Immerman's quantifier-free projection reductions). However, Dlogtime many-one reductions are not closed under composition (and Immerman's quantifier-free projection reductions are hard to explain to the non-specialist), and they still don't capture the really extremely weak nature of typical reductions.
So AC0 many-one reductions are used as a reasonably weak (and provably so) notion of reduction, which still works with common notions that are sufficiently easy to explain. But it unfolds into quite a number of different notions, like circuit classes and the distinction between uniform and non-uniform, or like many-one reductions and hence function classes. Here, the devil is in the details, like really understanding Dlogtime-uniformity, or making sense of function classes for alternating Turing machines, given the fact that the logarithmic time hierarchy (LH) is equal to Dlogtime-uniform AC0. And even that non-uniform vs. P-uniform vs. Dlogtime-uniform issue is not as clear cut as one would hope, see the discussion in the answer here about details behind Algebra, Logic and Complexity in Celebration of Eric Allender and Mike Saks by Neil Immerman.
-
$\begingroup$ "Dlogtime many-one reductions are not closed under composition" Are you referring to Dlogtime $AC^0$ reductions? Do you think you could explain what the issue is here? Thanks! $\endgroup$ Oct 23, 2020 at 19:28
-
$\begingroup$ @LorenzoNajt I really refer to Dlogtime itself, in the sense of the lowest class in the logarithmic time hierarchy. I initially had a hard time myself understanding why Sam Buss wrote “..., we shall use the yet stronger property (c) of deterministic log time reducibility. Although it is not transitive, ...” All the individual classes in the logarithmic time hierarchy are not closed under composition. A circuit of depth m as input to a circuit of depth n gives a depth m+n cir. $\endgroup$ Oct 24, 2020 at 22:01
-
$\begingroup$ I'm still confused. It seems like it should be true that if $L$ reduces to $L'$ via a DLOGTIME uniform $AC^0$ circuit family, and similarly for $L'$ to $L''$, then $L$ reduces to $L''$ via a DLOGTIME uniform $AC^0$ family -- one doesn't have to compose the dlogtime machines, instead one builds a new dlogtime machine that recognizes the connection language of the composed circuit by running one of the previous two machines based on which half ($L$ to $L'$ or $L'$ to $L''$) of the circuit on is examining a connection within. $\endgroup$ Oct 30, 2020 at 20:20
-
$\begingroup$ As for an example of dlogtime not composing, a mentor suggested the following example to me (though correctness depends on the oracle model - i.e. whether one has to write down the input the oracle explicitly): We can define a dlogtime machine $M$ that computes the parity of the bits $x[i : i + \log(n)]$ on input $(x,i)$. A $\log(n)$ time machine that can make calls to $M$ (but without having to write $x$ on the oracle tape to call $M$ on $(x,i)$) can compute the parity of $\log(n)^2$ bits of its input string, which is not possible in dlogtime. $\endgroup$ Oct 30, 2020 at 20:25