The $\mathrm{NC} \stackrel?= \mathrm P$ question is not as famous as the $\mathrm P$ versus $\mathrm{NP}$ problem, but still a deep and interesting question. It is generally accepted that there are unlikely to be polylog-depth, polynomial size circuits for all problems in $\mathrm P$ — especially in the poly-time uniform setting (where we require the circuit to be specified by a polynomial-time algorithm).

However, if you have gates with unbounded fan-in and fan-out, one might still have exponential-size, polylog-depth circuits for $\mathrm P$, which are uniform in the sense of having a (logspace) succinct representation.

Definition (succinct circuits). Given a circuit with $n$ inputs, $k$ outputs, and $m$ gates, we represent the circuit by a directed acyclic graph with node labels $\{1,2,\ldots,n{\:\!+\:\!}m{\:\!+\:\!}k\}$, where the wires connecting the output of one gate to the input of another are represented by directed edges between the corresponding nodes. A succinct representation for the circuit is

  • a deterministic logspace algorithm which assigns the type (e.g. input, output, AND, OR, NOT, PARITY, etc.) to each node,

  • accompanied by a deterministic logspace algorithm for deciding the input/output relation (i.e. the adjacency relation in the digraph) for pairs of gates,

from binary encodings of the gate labels.

For instance, $3\textrm{-SAT}$ can be solved using a succinct AND-OR tree of depth 4, by using exponentially many sub-circuits, each of which tests a 3-CNF formula presented as input against a possible assignment to its variables: this gives rise to a circuit of constant depth. By considering log-space reductions of arbitrary problems in $\mathrm{P}$ to $3\textrm{-SAT}$ and using $\mathrm L \subseteq \mathrm{NC^2}$, it seems to me that we can obtain succinct $O(\log^2 n)$-depth circuits of size $2^{O(\mathrm{poly}\,n)}$ for any problem in $\mathrm P$ — where the polynomial in the exponent will be related to the deterministic run-time of the polynomial time algorithm for the problem in $\mathrm P$.

What exponential upper bounds are known for the size of succinct $O(\log^d n)$-depth circuits — boolean or arithmetic, with unbounded fan-in — for arbitrary problems in $\mathrm P$, for instance for $d \leqslant 4$?

  • 5
    $\begingroup$ For starters, any problem whatsoever has depth 2, fan-in $2^n$ circuits by using CNF (or DNF). Is width the same thing as fan-in? $\endgroup$ Aug 24 '16 at 16:25
  • $\begingroup$ @EmilJeřábek: Of course, I neglected to impose a uniformity condition. I'll revise my question. As to width: while we can define depth purely topologically, we can also define it by imposing a time-ordering on the gates of the circuit (including explicit fan-out operations), which are consistent with the orientation of the edges from outputs of gates to inputs of subsequent gates. This presents the circuit as a sequence of transformations $\{0,1\}^n \to \{0,1\}^{N_1} \to \{0,1\}^{N_2} \to \cdots$ on bitstrings. The width is then the maximum number $N_t$ of concurrent bits, over all $t \ge 0$. $\endgroup$ Aug 25 '16 at 8:48
  • $\begingroup$ While the notion of width is part of what prompted me to consider this question, I can ultimately get to the meaning of my question by asking about circuit size instead, so I've revised it to address that instead. $\endgroup$ Aug 25 '16 at 9:20
  • $\begingroup$ For problems in P, the CNF or DNF circuits are succinct as in your definition. $\endgroup$ Aug 26 '16 at 7:15
  • $\begingroup$ Ah yes, I suppose I'm still leaving room for hard-coding. For logspace-concise circuits the same would still hold for proles in L, but that doesn't concern me so much. I'll revise the problem again. $\endgroup$ Aug 28 '16 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.