4
$\begingroup$

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)

[1] Complexity of converting a boolean circuit to a boolean formula

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – vzn Nov 3 '13 at 16:31
  • $\begingroup$ @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. $\endgroup$ – Stasys Nov 3 '13 at 19:49
  • $\begingroup$ 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...?) $\endgroup$ – vzn Nov 4 '13 at 1:47
  • $\begingroup$ thx for ref, Rossman has now archived his paper at ECCC. Formulas vs. Circuits for Small Distance Connectivity $\endgroup$ – vzn Dec 2 '13 at 19:27
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1 thx/helpful but am looking for a P/poly vs NP thm related to trees/formulas (ie higher/above P complexity) $\endgroup$ – vzn Nov 1 '13 at 23:29
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Nov 1 '13 at 23:34
  • $\begingroup$ interested in any ref related to polysize formulas $\subsetneq$ P/poly. also, edited question somewhat. $\endgroup$ – vzn Nov 2 '13 at 1:42
  • 3
    $\begingroup$ @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/… $\endgroup$ – Joshua Grochow Nov 2 '13 at 3:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Stasys Nov 2 '13 at 13:24

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.