I've seen poly-time and logspace uniformity for circuit families, typically defined as the existence of a poly-time/logspace Turing machine "generator" that outputs the correctly sized circuit $C_n$ on input $n$. These restrictions upper bound the power of circuit families by requiring that they are computationally generated.

I was wondering what happens when you change the generator model. Here are two (vague) questions:

  1. Are there other useful types of uniformity for circuit families?
  2. Are there interesting "generators" besides time/space bounded TMs? For example, consider families that progress from $C_i$ to $C_{i+1}$ by "small" modifications of the circuit. Can these be broad and have interesting complexity properties?

The idea in #2 is far too inclusive, since it allows things like simple recursive definitions. I am more interested in severe restrictions on the range of possible families by limiting the types of modifications.


When you want to define (fully) uniform versions of circuit classes, log-space or poly-time uniformity is only sensible for classes of circuits whose power exceeds log-space or poly-time, respectively. This means that poly-time uniformity is next to useless, and log-space uniformity is good for classes like P, NC, $\mathrm{NC}^{k+1}$, $\mathrm{AC}^k$ for $k\ge1$, but not, say, for $\mathrm{NC}^1$.

The standard notion of uniformity for small complexity classes is DLOGTIME-uniformity, where furthermore one has to be careful what exact kind of description of the circuit is asked to be computable in DLOGTIME: in cases where it matters (e.g., $\mathrm{NC}^1$), one needs to use the extended connection language (cf. Ruzzo) of the circuit. This is known as $U_E$-uniformity.


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.