16
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can you elaborate on the meaning of "practically has the same power"? $\endgroup$ – M.S. Dousti Sep 26 '10 at 18:30
  • $\begingroup$ 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. $\endgroup$ – Gil Kalai Sep 29 '10 at 1:23
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Shor Nov 2 '10 at 3:58
8
$\begingroup$

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

|cite|improve this answer
$\endgroup$
7
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Link to the paper: dx.doi.org/10.1016/0022-0000(90)90022-D $\endgroup$ – Suresh Venkat Sep 24 '10 at 4:29
  • $\begingroup$ 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) ? $\endgroup$ – M. Alaggan Nov 1 '10 at 6:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Srikanth Nov 1 '10 at 20:45
  • $\begingroup$ 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 :) $\endgroup$ – M. Alaggan Nov 2 '10 at 3:32
  • $\begingroup$ 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. $\endgroup$ – Peter Shor Nov 3 '10 at 14:52
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ A LOGSPACE generator for the circuit will also work fine to capture P. $\endgroup$ – Peter Shor Nov 2 '10 at 17:18
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 26 '12 at 11:54
  • $\begingroup$ @Emil, you are correct, thanks for noticing the mistake, it should be $AltTime(O(1),O(\lg n))$. $\endgroup$ – Kaveh Apr 26 '12 at 16:18
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.