<p>I think the answer to you first question is negative: A circuit has a fixed number of inputs, and thus, IMO, we can only talk about "families" of circuits, rather than just one uniform circuit.</p>

<p>Regarding your second question, you may note that there are "uniform families of circuits," whose description is generated by a Turing machine. That is, let $\{C_n\}$ be a uniform family of circuit, and let $M$ be a Turing machine. Then, for each $n$, $[C_n] = M(1^n)$, where $[C_n]$ denotes the description of $C_n$.</p>

<p>There are several complexity classes below P, defined by uniform families of circuits. For example:</p>

<p>$\mathbf{NC}^i$ is the class of decision problems decidable by <strong>uniform</strong> boolean circuits with a polynomial number of gates and depth $O(\log^i n)$.</p>

CC BY-SA 2.5
2010-09-23T21:41:55.323Z
2010-09-23T21:41:55.323Z
Sadeq Dousti
<p>Adding to Sadeq's answer above, as one looks at circuit classes contained in P, one might also want to look at more and more restrictive notions of uniformity.</p>

<p>The simplest and most well-known notion is P-uniformity, which is the requirement that there is a (deterministic) Turing Machine M that produces circuit $C_n$ in time poly(n) (Suresh talks of this also). The more restrictive versions of uniformity try to limit the power of M further. For example, there is also Logspace-uniformity, where M is now required to run in space O(log(n)). </p>

<p>The most restrictive notion that I know of is DLOGTIME-uniformity, which is used for small circuit classes. Here, the (now random-access) machine M only has time O(log n) and hence cannot possibly write down the description of the entire circuit. The condition imposed is that given i and n, M can write down the ith bit of the description of the circuit in time O(log n).</p>

<p>For more, see the following paper: David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306 (1990).</p>

CC BY-SA 2.5
2010-09-24T04:29:08.933Z
Link to the paper: http://dx.doi.org/10.1016/0022-0000(90)90022-D
Suresh Venkat
CC BY-SA 2.5
2010-11-01T06:36:46.023Z
If M is going to write the i-th bit of the description of the circuit in O(log n), doesn't that means if the circuit is of size O(n) then it is equivalent to allowing the machine to generate the entire circuit in O(n log n) ?
Mohammad Alaggan
CC BY-SA 2.5
2010-11-01T20:45:18.687Z
It does not seem to be equivalent. What you have shown is that the above (Barrington et. al.) notion of uniformity is at least as strong as the notion of uniformity you propose. The converse it not clear. Specifically, it is not clear to me if the following is true: given a family of circuits of size $O(n)$ that can be generated by a TM in time $O(n\log n)$, come up with a TM that, given $i$ and $n$, generates the $i$th bits of $C_n$ in time $O(\log n)$. In fact, I don't think it is true.
Srikanth
CC BY-SA 2.5
2010-11-02T03:32:09.867Z
I agree, a counter example would be a TM that, given $i$ and $n$, generates the $i$th bit in $O(1)$, except for the last bit for which it takes $O(n \log n)$. Thanks for the hint :)
Mohammad Alaggan
CC BY-SA 2.5
2010-11-03T14:52:00.603Z
The point is not that X-uniform families of circuits give the same sets of families for different X, but that the functions which can be computed by X-uniform families of circuits are the same for different X.
Peter Shor 
CC BY-SA 2.5
2010-11-04T04:49:41.433Z
Fair enough. But I don't see a (generic) way of generating, with fewer resources, a different family of circuits that computes the same function.
Srikanth
CC BY-SA 2.5
2010-11-05T18:31:12.863Z
One way to do this is to start with a P-uniform family of circuits, find a Turing machine which computes the same function, and then use a LOGSPACE generator to build a circuit family in which the different bits tell which symbol is in a given spot on the tape of the Turing machine at time $t$. This has quite a bit of overhead, but not more than polynomial.
Peter Shor 
CC BY-SA 2.5
2010-11-06T04:21:05.557Z
Great point! You are absolutely right. What you show implies that P-uniform P/poly = LOGSPACE-uniform P/poly. However, note that you don't have a good handle on many parameters of the circuit produced by your LOGSPACE generator, most notably depth. Hence, it is unclear, for example, if LOGSPACE-uniform $AC^0$ is the same as P-uniform $AC^0$. In fact, assuming, say, that $DSPACE(n)$ does not contain $DTIME(2^{O(n)})$ (which is reasonable), I think one can come up with functions that can be computed by a P-uniform $AC^0$ but not by a LOGSPACE-uniform $AC^0$.
Srikanth
CC BY-SA 2.5
2010-11-06T17:04:06.727Z
Hi Srikanth, I wouldn't expect LOGSPACE-uniform AC$^0$ to be the same as P-uniform AC$^0$. In general, you need to make sure the Turing machine building the circuit is no more powerful than the complexity class you want the circuit to compute (otherwise it can hide undesired information in the circuit, in the same way information can be hid in non-uniform circuits). This means defining uniform circuits for very low complexity classes is quite tricky. For uniform $AC^0$ circuits, e.g., you need to build them with very weak machines. See the reference you cite above for more details.
Peter Shor 
CC BY-SA 2.5
2010-09-23T22:22:48.217Z
2010-09-23T22:22:48.217Z
Srikanth
<p>One way to "unify" circuits and uniform computations is to require a complexity limited procedure that takes $n$ and outputs the advice circuit $C_n$. In the case of P, I believe that requiring a polynomialtime generator that can do the above will capture P correctly. </p>

CC BY-SA 2.5
2010-11-02T17:18:47.023Z
A LOGSPACE generator for the circuit will also work fine to capture P.
Peter Shor 
CC BY-SA 2.5
2010-09-23T21:39:13.403Z
2010-09-23T21:39:13.403Z
Suresh Venkat
<blockquote>
  <p>It there a description of uniformity just in terms of circuits?</p>
</blockquote>

<p>If by "in terms of circuits" you mean nonuniform circuits then the answer is negative. If the description of circuits is not uniform, it will allow non-computable functions to be used to define circuits which in turn will be able to compute non-computable functions. We can always build a circuit of size $1$ computing $f(|x|)$ where $f$ is a function computable by whatever means we are using to describe the circuits.</p>

<p>On the other hand, if we are allowed to restrict to uniform circuits to define the circuits, then the answer is obviously positive. And we can use $FO$ (which is equal to $DLogTime$ and uniform $AC^0$) to define uniformity. $FO$ is conceptually very close to circuits.</p>

<p>It seems to me that the main point here is that we need some model of uniform computation to define uniformity for circuits, if the description of circuits is given by means which are not uniform, the circuits can be nonuniform.</p>

CC BY-SA 3.0
2012-04-26T11:54:07.693Z
FO is not equal to DLogTime, but to alternating log-time with $O(1)$ alternations. However, for many natural classes of circuits, DLogTime-uniformity and FO-uniformity coincide.
Emil Jeřábek
CC BY-SA 3.0
2012-04-26T16:18:56.323Z
@Emil, you are correct, thanks for noticing the mistake, it should be $AltTime(O(1),O(\lg n))$.
Kaveh
CC BY-SA 2.5
2010-11-02T03:00:22.577Z
2010-11-02T03:06:24.177Z
2010-11-02T03:06:24.177Z
Kaveh
<p>One gap that I was always aware that I don't really understand is between non uniform and uniform computational complexity where the circuit complexity represents the non uniform version and Turing machines is were things are uniform. I suppose "uniform" is a way to restrain the class of algorithms, e.g. not allowing an entirely different circuit for a problem with n variables compared to a problem of n+1 variables. </p>

<p>My questions are: 1) It there a description of uniformity just in terms of circuits, and 2) Is it possible to come with an even stronger form of uniformity and thus to give even more restricted notion of what effective (or restrained) algorithms in P are? </p>

<p>Late clarification: my intention in question 2 is about a restricted class of algorithms that "practically" has the same power as the class of polynomial algorithms.</p>

CC BY-SA 2.5
2010-09-26T18:30:27.943Z
Can you elaborate on the meaning of "practically has the same power"?
Sadeq Dousti
CC BY-SA 2.5
2010-09-29T01:23:47.293Z
I mean that all algorithms in P we encounter practically are in this (hypothetical) restricted class. So I do not mean classes which are known (or are conjectured) to omit specific polynomial type algorithm like AC_0 or NC^i are  not what I refer to.
Gil Kalai
CC BY-SA 2.5
2010-11-02T03:58:14.273Z
For question 2, the class of functions computable by LOGSPACE-uniform circuits of polynomial size is P. (And you will still get P even with some complexity classes smaller than LOGSPACE if you define uniformity properly.) So imposing stricter uniformity conditions doesn't generally reduce the power of polynomial-time algorithms.
Peter Shor 
<cc.complexity-theory><circuit-complexity>
Stronger notions of uniformizations?
Gil Kalai
# Stronger notions of uniformizations?

(Asked by: username_0 on 2010-09-23)

One gap that I was always aware that I don't really understand is between non uniform and uniform computational complexity where the circuit complexity represents the non uniform version and Turing machines is were things are uniform. I suppose "uniform" is a way to restrain the class of algorithms, e.g. not allowing an entirely different circuit for a problem with n variables compared to a problem of n+1 variables.

My questions are: 1) It there a description of uniformity just in terms of circuits, and 2) Is it possible to come with an even stronger form of uniformity and thus to give even more restricted notion of what effective (or restrained) algorithms in P are?

Late clarification: my intention in question 2 is about a restricted class of algorithms that "practically" has the same power as the class of polynomial algorithms.

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: Can you elaborate on the meaning of "practically has the same power"?  
> **username_0**: I mean that all algorithms in P we encounter practically are in this (hypothetical) restricted class. So I do not mean classes which are known (or are conjectured) to omit specific polynomial type algorithm like AC_0 or NC^i are  not what I refer to.  
> **username_2**: For question 2, the class of functions computable by LOGSPACE-uniform circuits of polynomial size is P. (And you will still get P even with some complexity classes smaller than LOGSPACE if you define uniformity properly.) So imposing stricter uniformity conditions doesn't generally reduce the power of polynomial-time algorithms.  

---

## 4 answers

### Answer by username_1 on 2010-09-23. Score: 8

I think the answer to you first question is negative: A circuit has a fixed number of inputs, and thus, IMO, we can only talk about "families" of circuits, rather than just one uniform circuit.

Regarding your second question, you may note that there are "uniform families of circuits," whose description is generated by a Turing machine. That is, let $\{C\_n\}$ be a uniform family of circuit, and let $M$ be a Turing machine. Then, for each $n$, $[C\_n] = M(1^n)$, where $[C\_n]$ denotes the description of $C\_n$.

There are several complexity classes below P, defined by uniform families of circuits. For example:

$\mathbf{NC}^i$ is the class of decision problems decidable by **uniform** boolean circuits with a polynomial number of gates and depth $O(\log^i n)$.


---

### Answer by username_3 on 2010-09-23. Score: 7

Adding to Sadeq's answer above, as one looks at circuit classes contained in P, one might also want to look at more and more restrictive notions of uniformity.

The simplest and most well-known notion is P-uniformity, which is the requirement that there is a (deterministic) Turing Machine M that produces circuit $C\_n$ in time poly(n) (Suresh talks of this also). The more restrictive versions of uniformity try to limit the power of M further. For example, there is also Logspace-uniformity, where M is now required to run in space O(log(n)).

The most restrictive notion that I know of is DLOGTIME-uniformity, which is used for small circuit classes. Here, the (now random-access) machine M only has time O(log n) and hence cannot possibly write down the description of the entire circuit. The condition imposed is that given i and n, M can write down the ith bit of the description of the circuit in time O(log n).

For more, see the following paper: David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306 (1990).

> **Comments:**
> **username_4**: Link to the paper: http://dx.doi.org/10.1016/0022-0000(90)90022-D  
> **username_5**: If M is going to write the i-th bit of the description of the circuit in O(log n), doesn't that means if the circuit is of size O(n) then it is equivalent to allowing the machine to generate the entire circuit in O(n log n) ?  
> **username_3**: It does not seem to be equivalent. What you have shown is that the above (Barrington et. al.) notion of uniformity is at least as strong as the notion of uniformity you propose. The converse it not clear. Specifically, it is not clear to me if the following is true: given a family of circuits of size $O(n)$ that can be generated by a TM in time $O(n\log n)$, come up with a TM that, given $i$ and $n$, generates the $i$th bits of $C_n$ in time $O(\log n)$. In fact, I don't think it is true.  
> **username_5**: I agree, a counter example would be a TM that, given $i$ and $n$, generates the $i$th bit in $O(1)$, except for the last bit for which it takes $O(n \log n)$. Thanks for the hint :)  
> **username_2**: The point is not that X-uniform families of circuits give the same sets of families for different X, but that the functions which can be computed by X-uniform families of circuits are the same for different X.  
> **username_3**: Fair enough. But I don't see a (generic) way of generating, with fewer resources, a different family of circuits that computes the same function.  
> **username_2**: One way to do this is to start with a P-uniform family of circuits, find a Turing machine which computes the same function, and then use a LOGSPACE generator to build a circuit family in which the different bits tell which symbol is in a given spot on the tape of the Turing machine at time $t$. This has quite a bit of overhead, but not more than polynomial.  
> **username_3**: Great point! You are absolutely right. What you show implies that P-uniform P/poly = LOGSPACE-uniform P/poly. However, note that you don't have a good handle on many parameters of the circuit produced by your LOGSPACE generator, most notably depth. Hence, it is unclear, for example, if LOGSPACE-uniform $AC^0$ is the same as P-uniform $AC^0$. In fact, assuming, say, that $DSPACE(n)$ does not contain $DTIME(2^{O(n)})$ (which is reasonable), I think one can come up with functions that can be computed by a P-uniform $AC^0$ but not by a LOGSPACE-uniform $AC^0$.  
> **username_2**: Hi username_3, I wouldn't expect LOGSPACE-uniform AC$^0$ to be the same as P-uniform AC$^0$. In general, you need to make sure the Turing machine building the circuit is no more powerful than the complexity class you want the circuit to compute (otherwise it can hide undesired information in the circuit, in the same way information can be hid in non-uniform circuits). This means defining uniform circuits for very low complexity classes is quite tricky. For uniform $AC^0$ circuits, e.g., you need to build them with very weak machines. See the reference you cite above for more details.  

---

### Answer by username_4 on 2010-09-23. Score: 6

One way to "unify" circuits and uniform computations is to require a complexity limited procedure that takes $n$ and outputs the advice circuit $C\_n$. In the case of P, I believe that requiring a polynomialtime generator that can do the above will capture P correctly.

> **Comments:**
> **username_2**: A LOGSPACE generator for the circuit will also work fine to capture P.  

---

### Answer by username_6 on 2010-11-02. Score: 5

> It there a description of uniformity just in terms of circuits?

If by "in terms of circuits" you mean nonuniform circuits then the answer is negative. If the description of circuits is not uniform, it will allow non-computable functions to be used to define circuits which in turn will be able to compute non-computable functions. We can always build a circuit of size $1$ computing $f(|x|)$ where $f$ is a function computable by whatever means we are using to describe the circuits.

On the other hand, if we are allowed to restrict to uniform circuits to define the circuits, then the answer is obviously positive. And we can use $FO$ (which is equal to $DLogTime$ and uniform $AC^0$) to define uniformity. $FO$ is conceptually very close to circuits.

It seems to me that the main point here is that we need some model of uniform computation to define uniformity for circuits, if the description of circuits is given by means which are not uniform, the circuits can be nonuniform.

> **Comments:**
> **username_7**: FO is not equal to DLogTime, but to alternating log-time with $O(1)$ alternations. However, for many natural classes of circuits, DLogTime-uniformity and FO-uniformity coincide.  
> **username_6**: @Emil, you are correct, thanks for noticing the mistake, it should be $AltTime(O(1),O(\lg n))$.  

---

