<p>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$.</p>

<p>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. <a href="http://dx.doi.org/10.1016/0022-0000%2881%2990038-6">Ruzzo</a>) of the circuit. This is known as $U_E$-uniformity.</p>

CC BY-SA 3.0
2012-04-26T11:19:43.867Z
2012-04-26T11:19:43.867Z
Emil Jeřábek
<p>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.</p>

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

<blockquote>
  <ol>
  <li>Are there other useful types of uniformity for circuit families? </li>
  <li>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?</li>
  </ol>
</blockquote>

<p>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.</p>

<cc.complexity-theory><reference-request><circuit-complexity><circuit-families><uniformity>
Other types of uniformity for circuits (incl. by small modifications)
Lucas Cook
# Other types of uniformity for circuits (incl. by small modifications)

(Asked by: username_0 on 2012-04-26)

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.

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, circuit-families, uniformity

---

## 1 answers

### Answer by username_1 on 2012-04-26. Score: 8 | Accepted answer

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](http://dx.doi.org/10.1016/0022-0000%2881%2990038-6)) of the circuit. This is known as $U\_E$-uniformity.


---

