HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What does "AC0 many-one reduction" mean?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whatmeanoneac0reductiondoesmany

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#92856, answer score: 8

Revisions (0)

No revisions yet.