What does the AC0 complexity class mean?

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.

Originally answered on Quora: https://www.quora.com/What-does-the-AC0-complexity-class-mean/answer/Mark-Gritter

Further reading:

• AC (complexity) -- Wikipedia
• AC^0 -- Complexity Zoo
• "Why is PARITY not in AC^0 important?"