<p>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 <a href="http://www.math.ucsd.edu/~sbuss/CourseWeb/Math262A_2013F/Scribe02.pdf" rel="noreferrer">lecture notes</a> for a detailed presentation. Of course this does not rule out a separation of $2^{\Omega(n)}$. </p>

<p>To the best of my knowledge the biggest separation known currently is $n^{3-o(1)}$ (over the de&nbsp;Morgan basis). It was <a href="http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366876-abs.html" rel="noreferrer">proved by Håstad</a> 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 <a href="http://www.math.rutgers.edu/~sk1233/courses/topics-S13/lec2.pdf" rel="noreferrer">these notes</a> for Andreev's proof. Håstad's bound is essentially tight for Andreev's method.</p>

<p>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. </p>

CC BY-SA 3.0
2014-08-28T11:35:37.840Z
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. :)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-08-25T14:49:30.510Z
2014-08-26T11:01:50.437Z
2014-08-26T11:01:50.437Z
Sasho Nikolov
<p>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$.</p>

<p>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.)</p>

<p>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?</p>

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

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

<p>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...</p>

CC BY-SA 3.0
2014-08-19T18:03:56.000Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-08-19T19:16:43.557Z
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.
Kaveh
CC BY-SA 3.0
2014-08-19T20:51:09.543Z
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)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-08-20T00:16:04.553Z
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 http://www.math.rutgers.edu/~sk1233/courses/topics-S13/lec2.pdf.
Sasho Nikolov
CC BY-SA 3.0
2014-08-20T14:09:42.933Z
@SashoNikolov: Thanks! In the course notes you give, I can only find $\Omega(n^{2.5 - \epsilon})$. Still, I am surprised, is nothing known about examples of formula complexity $\Omega(n^k)$ for any $k$? (For circuit complexity $\Theta(n)$.)
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-08-20T15:19:21.923Z
Hastad improved Andreev's bound http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366876-abs.html. I dont think a better formula lower bound is known for any explicit function.
Sasho Nikolov
CC BY-SA 3.0
2014-08-25T12:02:59.537Z
@SashoNikolov: I have looked up more information about your first comment, but I don't understand where the circuit complexity and formula complexity upper bounds that you give are coming from, could you provide a source, or tell me more about the reasoning? Thanks! As for the Hastad bound, I agree with you, at least there seems to be no better example in chapter 6 of the ''Boolean Function Complexity'' book. You are welcome to post this as an answer. :)
Antoine Amarilli 'a3nm'
<boolean-functions><circuit-families><boolean-formulas>
May Boolean circuits be exponentially more concise than Boolean formulae?
Antoine Amarilli 'a3nm'
# May Boolean circuits be exponentially more concise than Boolean formulae?

(Asked by: username_0 on 2014-08-19)

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

**Tags:** boolean-functions, circuit-families, boolean-formulas
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: 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)  
> **username_1**: 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 http://www.math.rutgers.edu/~sk1233/courses/topics-S13/lec2.pdf.  
> **username_0**: @SashoNikolov: Thanks! In the course notes you give, I can only find $\Omega(n^{2.5 - \epsilon})$. Still, I am surprised, is nothing known about examples of formula complexity $\Omega(n^k)$ for any $k$? (For circuit complexity $\Theta(n)$.)  
> **username_1**: Hastad improved Andreev's bound http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366876-abs.html. I dont think a better formula lower bound is known for any explicit function.  
> **username_0**: @SashoNikolov: I have looked up more information about your first comment, but I don't understand where the circuit complexity and formula complexity upper bounds that you give are coming from, could you provide a source, or tell me more about the reasoning? Thanks! As for the Hastad bound, I agree with you, at least there seems to be no better example in chapter 6 of the ''Boolean Function Complexity'' book. You are welcome to post this as an answer. :)  

---

## 1 answers

### Answer by username_1 on 2014-08-25. Score: 11 | Accepted answer

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](http://www.math.ucsd.edu/~sbuss/CourseWeb/Math262A_2013F/Scribe02.pdf) 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](http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366876-abs.html) 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](http://www.math.rutgers.edu/~sk1233/courses/topics-S13/lec2.pdf) 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.

> **Comments:**
> **username_0**: 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. :)  

---

