Stronger notions of uniformizations?

Question

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.

Answer 1

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 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

1) Is there a description of uniformity just in terms of circuits?

[This is an edited version of my reply to the same question you asked on Dick Lipton's blog. Caveat: I'm not an expert.]

Yes (I think), of at least two different kinds:

a) The circuits are generatable by a Turing machine in polynomial time in the problem input size (as mentioned in some other replies). (I think this is the standard definition of the concept.)

This covers any circuit family that we could want to call uniform, but as a definition of the concept of P-time, it just reduces the definition on circuit families to the definition on Turing machines, which might not be what you want.

b) If there is a 1-dimensional cellular automaton which evolves the problem input to the problem solution (for a decision problem, the solution would be a single bit in a specified cell relative to the cells containing the input, which is a stable state of the CA), in polynomial time in input size, then this corresponds to a circuit which is periodic in 2D in a simple way (one repeat unit per cell per time-unit), and whose state only matters in a quadratically large region relative to the solution time.

This is a very special kind of uniform circuit family, but sufficient to solve all problems in P, since a Turing machine can be easily encoded as a 1D CA. (This also appears to satisfy the definition of DLOGTIME-uniformity mentioned in an earlier reply.)

(This is similar to the encodings of Turing machines as circuits mentioned in Gowers’ replies on Lipton's blog — in fact, one of them is probably identical.)

One way to encode a Turing machine as a 1D CA: in each cell, we represent the tape state at one point, the state the turing machine head would have if it were here now (whose value doesn’t matter if it’s not here), and one bit saying whether the head is here now. Clearly, each such state at time t only depends on its immediate neighborhood states at time t-1, which is all we need for this to work as a CA.