5
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 1
    $\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$ – Thomas Klimpel Jun 8 '18 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 '18 at 21:21
4
$\begingroup$

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.

$\endgroup$

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.