circuit complexity

Basic classes:

NC (Nick's class): Boolean circuits with fan-in 2

AC (alternating circuits): Boolean circuits with unlimited fan-in for AND/OR gates

TC (threshold circuits): adds 'threshold' gates, with unlimited fan-in, that test if a (weighted) majority of inputs are true. (models the behavior of neurons in artificial neural nets)

These are for decision problems, so all circuits have $n$ Boolean inputs and one output (the decision). Each class has variants $TC^0, TC^1, \ldots$ where $TC^{(k)}$ allows circuits with depth $(\log n)^k$, and the class $TC$ is taken to be the union of all of these (polylogarithmic depth), and similarly for NC and AC.

For the constant-depth variants, we have $NC^0 \subset AC^0 \subset TC^0$, where

• $NC^0 \subset AC^0$ simply by considering any function that depends on all the bits of the input, and noting that $NC^0$ can't express such functions.
• $AC^0 \subset TC^0$ by considering the parity or majority functions, which are known to not be in $AC^0$.

For the polylog-depth variants, we have $NC = AC = TC$ since the more advanced 'features' can be simulated in the simpler classes by polylog-depth gadgets.

Uniformity: When we talk about circuits as a function of input length $n$, we generally don't allow an arbitrarily different circuit for each $n$ - this could smuggle in noncomputable information. We usually require that there is some simple machine that can generate circuits for arbitrary $n$. The standard assumption is DLOGTIME-Uniform, which requires a machine that runs in logarithmic time and can answer any local query about the circuit (the type of any given gate, and if/how any two gates are connected).It has to be local queries because just to even print the whole circuit would require polynomial time, which is too generous a restriction. Logarithmic time for a local query is just enough to read the indices of the gates (which are themselves $\log n$) and do simple lookup-like operations on them.