7
$\begingroup$

Consider a family $(f_n)_{1 \leq n}$ of Boolean functions, where $f_n$ is a function on $n$ variables. Consider for every $n$ the smallest Boolean formula $F_n$ describing $f_n$, and the smallest Boolean circuit $C_n$ describing $f_n$. Say we have $|F_n| = \Omega(g(|C_n|))$ for a certain function $g$.

What is the fastest-growing $g$ for which this is known to be possible, and the slowest-growing $g$ for which it is known to be impossible? (From the comments, it seems like there is still a gap here, but I'm trying to understand which one.)

This is the "simple" version of my question. What I am interested in is a multi-output, probabilistic (=weighted), variant of the problem, defined as follows. It is clear how to extend circuits to be multi-output, and I define a $k$-output formula to be just a $k$-tuple of formulas on the same inputs. I say that the input variables have a certain probability of being true (written in binary and accounted for in the circuit or formula size), each independently from the others, and I look at the probability distribution on the tuple of outputs (forgetting which input is yielding which output, just looking at the distribution on values), given this product distribution on the inputs, in the circuit and formula context. Here again the circuits are certainly more concise than formulae, but how much? Are there some distributions that can be exponentially more concise to represent with circuits, intuitively because of sub-expression reuse?

To give an example for this more elaborate version, consider the following distribution on $n$ outputs:

  • $000 \cdots 00$ with probability $1/2$,
  • $100 \cdots 00$ with probability $1/4$,
  • $110 \cdots 00$ with probability $1/8$,
  • ...
  • $111 \cdots 10$ with probability $1/2^n$,
  • $111 \cdots 11$ with probability $1/2^n$.

There is a multi-output probabilistic circuit of size $O(n)$ which generates this (and reuses the draw of the $i$-th bit to draw the $(i+1)$-th). By contrast, the straightforward Boolean function encoding of this is quadratic, and I can't see how you could make it shorter but yet cannot prove it...

$\endgroup$
  • 2
    $\begingroup$ Remember that the circuit complexity of any boolean function is in $[1, (1+o(n))2^n/n]$, and the formula complexity is in $[1, (1+o(1))2^n/\log n]$, so a separation quite as strong as you propose should not be possible. Otherwise, separating poly-size formulas and circuits is a well-known open problem in complexity theory, and is most likely well out of reach. In standard terms, this is the problem of separating nonuniform NC1 and P/poly. $\endgroup$ – Sasho Nikolov Aug 19 '14 at 18:03
  • $\begingroup$ You need string formula-size lower bounds for explicit functions (I am interpreting your "simple" as explicit, i.e. being in $\mathsf{NP}$) and we don't have such lower bounds. The only known strong lower bounds for explicit functions are for bounded depth. $\endgroup$ – Kaveh Aug 19 '14 at 19:16
  • $\begingroup$ Thanks for your comments! In the light of this, I have rephrased my question more generally, asking for which bounds are known about the gap. (Maybe they follow from your comments, I'm not familiar enough with the notions to understand them but I will investigate.) Also, as the absence of exponential separation surprises me, I have also added a description of the actual problem I am interested in, rather than the simplified formulation I had tried to phrase at first. I hope it is not too far removed from the simplified question (maybe some dimensions of the problem statement are not useful) $\endgroup$ – a3nm Aug 19 '14 at 20:51
  • 2
    $\begingroup$ Over the de Morgan basis, I think that parity has linear size circuits and formula complexity $\Theta(n^2)$. I think there is also a less natural boolean function which has linear size circuits and formula complexity $\Theta(n^3)$. Check this math.rutgers.edu/~sk1233/courses/topics-S13/lec2.pdf. $\endgroup$ – Sasho Nikolov Aug 20 '14 at 0:16
  • 2
    $\begingroup$ Hastad improved Andreev's bound computer.org/csdl/proceedings/focs/1993/4370/00/…. I dont think a better formula lower bound is known for any explicit function. $\endgroup$ – Sasho Nikolov Aug 20 '14 at 15:19
11
$\begingroup$

The circuit complexity of any boolean function of $n$ variables is at most $(1+o(1))2^n/n$, so a separation of between circuit and formula complexity of $\Omega(2^n)$ is not possible. This upper bound was established by Lupanov, and his method is known as the Lupanov representation of boolean functions. It also gives an upper bound of $(1+o(1))2^n/\log n$ for the formula complexity of any $n$-variable boolean function. See for example these lecture notes for a detailed presentation. Of course this does not rule out a separation of $2^{\Omega(n)}$.

To the best of my knowledge the biggest separation known currently is $n^{3-o(1)}$ (over the de Morgan basis). It was proved by Håstad for a function with linear circuit complexity. This was an improvement on the method of Andreev, who showed a formula size lower bound of $\Omega(n^{2.5})$ for the same function using the method of random restrictions. You can check these notes for Andreev's proof. Håstad's bound is essentially tight for Andreev's method.

The class of functions computable by polynomial size formulas coincides with (nonuniform) NC1 and the class of functions computable by polysize circuits is P/poly. Separating these two classes is a well-known open problem in complexity theory, and is almost certainly well out of reach.

$\endgroup$
  • $\begingroup$ Thanks! Sadly this does not help me for the more complex formulation I was interested in, but as this answers my original question I accepted it. :) $\endgroup$ – a3nm Aug 28 '14 at 11:35

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.