# P/poly vs NP separation based on circuit trees instead of DAGs

there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast,

are there theorems/conjectures that relate P/poly vs NP separation to the size of circuit trees (aka formulas)?

note of course that CNF/SAT is a boolean formula. an example in this form would be something like if a CNF circuit family $C_n$ requires size $\Omega(g(n))$ clauses to compute function $f$ (alternately, can compute $f'$ in $O(g'(n))$ clauses) then NP $\not\subset$ P/poly, but the question is not limited to CNF & is asking about formulas in general. ([1] is a somewhat related question)

• your example is a bit odd: you are saying that the existence of a small-size formula for some problem would imply a class separation. but usually such a thing implies a collapse. do you have something in mind? Nov 1, 2013 at 23:39
• oops messed up the order of NP $\not\subset$ P/poly, edited that. as to your question that is reminiscent of this other question proving lower bounds by proving upper bounds
– vzn
Nov 2, 2013 at 0:35
• found this question by gowers somewhat similar are there super poly formula bounds & is formula size similar to circuit size
– vzn
Nov 9, 2013 at 19:12

As Sasho suggested, I am putting my comment as an answer.

The separations between monotone versions of $\mathsf{NC}^1/\mathsf{poly}$ and $\mathsf{P/poly}$ versions of complexity are long known (Karchmer-Wigderson, Grigni-Sipser, etc), but in the non-monotone world almost nothing was known. Fortunately, Ben Rossman has recently found the first separation of formulas vs. circuits in the bounded depth setting.

Let $\mathrm{Circuit}(S,d)$ (resp., $\mathrm{Formula}(S,d)$) denote the set of all boolean functions computable by unbounded fanin circuits (resp. formulas) of depth $\leq d$ and size $\leq S$. It is clear that $$\mathrm{Circuit}(S,d) \subseteq \mathrm{Formula}(S^d,d).$$ In particular, $$\mathrm{Circuit}(n^{O(1)},d) \subseteq \mathrm{Formula}(n^{O(d)},d).$$ What Ben has shown is that, if $d=d(n)\leq \log\log\log n$, then $$\mathrm{Circuit}(n^{O(1)},d) \not\subseteq \mathrm{Formula}(n^{o(d)},d).$$ Even more important is that he shows this separation on an explicit and basic function $\mathrm{STCONN}(n,k)$: given an $n$-vertex graph, decide whether it has an $s$-$t$ path of length $\leq k$. This function is in $\mathrm{Circuit}(n^{O(1)},\log k)$. His main result is: if $dk^3\leq \log n/\log\log n$ then $$\mathrm{STCONN}(n,k)\in \mathrm{Formula}(S,d)\ \Longrightarrow\ S\geq n^{\Omega(\log k)}.$$ This implies a tight depth lower bound: if $k\leq \log\log n$ then $$\mathrm{STCONN}(n,k)\in \mathrm{Circuit}(n^{O(1)},d)\ \Longrightarrow\ d=\Theta(\log k).$$ The existing techniques for small-depth circuit -- namely switching lemmas and approximation by low-degree polynomials-- do not distinguish between formulas and circuits due to their bottom-up nature. Top-down arguments, as Karchmer-Wigderson games, are difficult to realize in the non-monotone case. What Ben uses is a combination of these arguments.

• thx! reviewing your notes, monotone circuits; do you think thm9.17, 9.18, or 9.25 (which are close to an answer to the question) could be strong enough for any P/poly$\stackrel{?}{=}$NP result, or not?
– vzn
Nov 3, 2013 at 16:31
• @vzn: The answer is "most probably - NO, unless we extend the arguments to work under the presence of "auxiliary variables". The thms you mentioned are just Razborov's approximation argument "in disguise" (a "symmetric version"). And he has proved here what we need to get it work in non-monotone case. People trying to extend his argument to non-monotone circuits should carefully read this paper to avoid disappointments. Nov 3, 2013 at 19:49
• was thinking along those lines & thought you might say that! yes, have heard of that paper yet strangely, there is almost/nearly no reaction to it or further analysis/commentary on it by anyone [incl your own highly/deeply comprehensive book!], eg in stark contrast to Natural Proofs [which also does not mention it]. so if it really is a significant "barrier" its an extremely low-profile one... & yet it has been proven that superpoly monotone lower bounds on slice functions are sufficient to separate P/poly from NP (and razborov has apparently never written anything on slice fns...?)
– vzn
Nov 4, 2013 at 1:47
• thx for ref, Rossman has now archived his paper at ECCC. Formulas vs. Circuits for Small Distance Connectivity
– vzn
Dec 2, 2013 at 19:27

The class of functions computable by formulas of polynomial size is equivalent to the (nonuniform) class $\mathsf{NC}^1$ of functions computable by (bounded fanin/fanout) circuits of logarithmic depth. Proving the two implications is a nice exercise. In one direction, you can recursively "untangle" each level of a circuit by creating copies of gates. This increases the size by a constant factor for each of the $O(\log n)$ levels of the circuit. The other direction is proven by balancing the tree of the formula.

Also, $\mathsf{NC}^1$ is equivalent, by Barrington's theorem, to width 5 polynomial size branching programs.

We know that the uniform version of $\mathsf{NC}^1$ is contained in $\mathsf{L} \subseteq \mathsf{P}$ ($\mathsf{L}$ stands for deterministic logspace). It is not known whether any of these containments is proper AFAIK. Also it is not known whether the non-uniform $\mathsf{NC}^1$ is a proper subset of $\mathsf{P/\text{poly}}$.

• +1 thx/helpful but am looking for a P/poly vs NP thm related to trees/formulas (ie higher/above P complexity)
– vzn
Nov 1, 2013 at 23:29
• what I am saying is that problems decidable by polysize formulas might be (and I think are believed to be) a proper subset of P/poly. so a separation between polysize formulas and NP is not known to imply anything about P/poly vs. NP. Nov 1, 2013 at 23:34
• interested in any ref related to polysize formulas $\subsetneq$ P/poly. also, edited question somewhat.
– vzn
Nov 2, 2013 at 1:42
• @vzn: Evidence that L is a strict subset of P can also be taken as evidence that NC^1 (=poly formula size) is a strict subset of P/poly. See this related question: cstheory.stackexchange.com/questions/19315/… Nov 2, 2013 at 3:29
• The separations between monotone versions of $\mathsf{NC}^1/\mathsf{poly}$ and $\mathsf{P/poly}$ are long known (Karchmer-Wigderson, Grigni-Sipser, etc), but in the non-monotone world almost nothing was known. Fortunately, Ben Rossman has recently found the first separation of formulas vs. circuits in the bounded depth setting. Nov 2, 2013 at 13:24