<p>The <span class="math-container">$\mathrm{NC} \stackrel?= \mathrm P$</span> question is not as famous as the <span class="math-container">$\mathrm P$</span> versus <span class="math-container">$\mathrm{NP}$</span> 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 <span class="math-container">$\mathrm P$</span> — especially in the poly-time uniform setting (where we require the circuit to be specified by a polynomial-time algorithm).</p>
<p>However, if you have gates with unbounded fan-in and fan-out, one might still have <em>exponential-size</em>, polylog-depth circuits for <span class="math-container">$\mathrm P$</span>, which are uniform in the sense of having a (logspace) <strong>succinct</strong> representation.</p>
<blockquote>
<p><strong>Definition</strong> (<em>succinct circuits</em>). Given a circuit with <span class="math-container">$n$</span> inputs, <span class="math-container">$k$</span> outputs, and <span class="math-container">$m$</span> gates, we represent the circuit by a directed acyclic graph with node labels <span class="math-container">$\{1,2,\ldots,n{\:\!+\:\!}m{\:\!+\:\!}k\}$</span>, where the wires connecting the output of one gate to the input of another are represented by directed edges between the corresponding nodes. A <strong>succinct</strong> representation for the circuit is</p>
<ul>
<li><p>a deterministic logspace algorithm which assigns the type (<em>e.g.</em> input, output, AND, OR, NOT, PARITY, <em>etc.</em>) to each node,</p>
</li>
<li><p>accompanied by a deterministic logspace algorithm for deciding the input/output relation (<em>i.e.</em> the adjacency relation in the digraph) for pairs of gates,</p>
</li>
</ul>
<p>from binary encodings of the gate labels.</p>
</blockquote>
<p>For instance, <span class="math-container">$3\textrm{-SAT}$</span> 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 <em>constant</em> depth. By considering log-space reductions of arbitrary problems in <span class="math-container">$\mathrm{P}$</span> to <span class="math-container">$3\textrm{-SAT}$</span> and using <span class="math-container">$\mathrm L \subseteq \mathrm{NC^2}$</span>, it seems to me that we can obtain succinct <span class="math-container">$O(\log^2 n)$</span>-depth circuits of size <span class="math-container">$2^{O(\mathrm{poly}\,n)}$</span> for any problem in <span class="math-container">$\mathrm P$</span> — where the polynomial in the exponent will be related to the deterministic run-time of the polynomial time algorithm for the problem in <span class="math-container">$\mathrm P$</span>.</p>
<p>What exponential upper bounds are known for the size of succinct <span class="math-container">$O(\log^d n)$</span>-depth circuits — boolean or arithmetic, with unbounded fan-in — for arbitrary problems in <span class="math-container">$\mathrm P$</span>, for instance for <span class="math-container">$d \leqslant 4$</span>?</p>

CC BY-SA 3.0
2016-08-24T16:25:22.530Z
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?
Emil Jeřábek
CC BY-SA 3.0
2016-08-25T08:48:39.923Z
@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$.
Niel de Beaudrap
CC BY-SA 3.0
2016-08-25T09:20:05.730Z
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.
Niel de Beaudrap
CC BY-SA 3.0
2016-08-26T07:15:26.853Z
For problems in P, the CNF or DNF circuits *are* succinct as in your definition.
Emil Jeřábek
CC BY-SA 3.0
2016-08-28T21:48:08.847Z
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.
Niel de Beaudrap
CC BY-SA 3.0
2016-08-29T18:28:25.090Z
@NieldeBeaudrap Whether this is useful to you or not.. *shrug!* Anyway-- this whole questions reminds me very vaguely of the cryptographic notion of "Time-Lock Puzzles." The crypto community ('as a whole,' let's say) currently conjectures that program obfuscation leads to "optimally-succinct/compact Time-Lock Puzzles;" i.e. see https://eprint.iacr.org/2015/514.pdf The formal "engine" at work here is an assumption that there exists "non-parallelizing languages" -- this notion strictly generalizes the idea that $\mathsf{P}\not\subseteq\mathsf{NC}.$ Perhaps the connection is interesting to you :)
Daniel Apon
CC BY-SA 3.0
2016-08-29T18:32:50.763Z
(If I may so plead: Please don't coincidentally kill off our obfuscators by proving too good of an exponential upper bound, thanks! :))
Daniel Apon
CC BY-SA 3.0
2018-04-13T19:24:36.370Z
These don't answer the question, but may be related: (1) lower bound on bounded-depth succinct algebraic circuits for perm [Jansen-Santhanam](https://doi.org/10.1007/978-3-642-22006-7_61), (2) algebraic natural proofs [Forbes-Shpilka-Volk](https://arxiv.org/abs/1701.05328) and [G.-Kumar-Saks-Saraf](https://arxiv.org/abs/1701.01717) (and see the more recent [Blaser-Ikenmeyer-Jindal-Lysikov](https://eccc.weizmann.ac.il/report/2018/064/)) use a notion of succinct hitting sets for algebraic circuits.
Joshua Grochow
<circuit-complexity><polynomial-time><circuit-depth>
Wide and shallow circuits for $\mathrm P$
Niel de Beaudrap
# Wide and shallow circuits for $\mathrm P$

(Asked by: username_0 on 2016-08-24)

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

**Tags:** circuit-complexity, polynomial-time, circuit-depth

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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$.  
> **username_0**: 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.  
> **username_1**: For problems in P, the CNF or DNF circuits *are* succinct as in your definition.  
> **username_0**: 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.  
> **username_2**: @NieldeBeaudrap Whether this is useful to you or not.. *shrug!* Anyway-- this whole questions reminds me very vaguely of the cryptographic notion of "Time-Lock Puzzles." The crypto community ('as a whole,' let's say) currently conjectures that program obfuscation leads to "optimally-succinct/compact Time-Lock Puzzles;" i.e. see https://eprint.iacr.org/2015/514.pdf The formal "engine" at work here is an assumption that there exists "non-parallelizing languages" -- this notion strictly generalizes the idea that $\mathsf{P}\not\subseteq\mathsf{NC}.$ Perhaps the connection is interesting to you :)  
> **username_2**: (If I may so plead: Please don't coincidentally kill off our obfuscators by proving too good of an exponential upper bound, thanks! :))  
> **username_3**: These don't answer the question, but may be related: (1) lower bound on bounded-depth succinct algebraic circuits for perm [Jansen-Santhanam](https://doi.org/10.1007/978-3-642-22006-7_61), (2) algebraic natural proofs [Forbes-Shpilka-Volk](https://arxiv.org/abs/1701.05328) and [G.-Kumar-Saks-Saraf](https://arxiv.org/abs/1701.01717) (and see the more recent [Blaser-Ikenmeyer-Jindal-Lysikov](https://eccc.weizmann.ac.il/report/2018/064/)) use a notion of succinct hitting sets for algebraic circuits.  

---

## 0 answers

