# Wide and shallow circuits for $\mathrm P$

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$$?

• 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? Aug 24 '16 at 16:25
• @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$. Aug 25 '16 at 8:48
• 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. Aug 25 '16 at 9:20
• For problems in P, the CNF or DNF circuits are succinct as in your definition. Aug 26 '16 at 7:15
• 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. Aug 28 '16 at 21:48