# What does the AC0 complexity class mean?

in #steemstem3 years ago

AC^0 is a circuit complexity class. It represents the set of decision problems that are solvable with a family of constant-depth unlimited-fanin polynomial-size circuits. Photo by Yung Chang on Unsplash.

Unpacking that:

• “Circuit”: a boolean function created with logic gates and wires.
• “Decision problems”: yes-or-no answers to whether a particular bit-string belongs in some set. However, in practice we will also talk about “functions” in AC^0 as well that output more than one bit.
• “Family”: unlike automata which have unbounded input, a circuit has only a fixed number of inputs. So to solve a problem of length n, we need a circuit with n inputs, and for a problem of length n+1 we need a circuit with n+1
inputs. Instead of specifying a single machine, we’re actually specifying an infinite number of machines, one for each input size.
• “Constant-depth”: the depth of a circuit is how many gates there are between any input and the output. So, circuits in this family must have a maximum depth, no matter how large n gets.
• “Unlimited-fanin”: each of our logic gates may take as many inputs as desired. (Some complexity classes only allow two-input gates.)
• “Polynomial-size”: the total number of gates is bounded by some polynomial in the size of the input, n. Diagram from Wikimedia Commons

Circuit families in AC^0 are sometimes required to be "uniform." A “uniformity” condition on circuits means that the circuit description can be generated by a Turing machine (usually subject to some resource constraints), given the size of the input. But in other contexts, a problem could be in AC^0 even if its circuit family was uncomputable. Conventions vary, so it's best to be explicit.

An example problem in AC^0: addition, or as a decision problem, “is x + y = z a valid addition”? (Note that propagating the carries one by one, like a ripple-carry adder, doesn’t work for AC^0 because that is a non-constant-depth construction.)

The canonical problem not in AC^0: computing the parity of the input.

AC^0 is the smallest member of the "alternating complexity" class AC^i, which are polynomial-sized circuits with depth (log n)^i.

Sort:

I wonder when these type of questions start appearing on musing so they can be answered there instead of on quora.

@stemq is actually a better home, but it seems doubly-redundant to ask a question there just to answer it myself (two separate posts) when I already answered it once on a different site. But the volume of questions on stemq is pretty low, and the quality of questions interesting to me on @musing is not high.

This story was recommended by Steeve to its users and upvoted by one or more of them. 