4
$\begingroup$

We define $S(\phi)$ of formula $\phi$ to be the number of computational gates in a minimal $\{\neg, \wedge, \vee\}$-formula computing $\phi$.

Conjecture. If $\phi_1(a_{11}, \dots, a_{1y_1})$, $\dots$, $\phi_x(a_{x1}, \dots, a_{xy_x})$ are arbitrary Boolean functions with pairwise disjoint sets of variables, then it follows that$$S\left(\phi_1\left(a_{11}, \dots, a_{1y_1}\right) \oplus \ldots \oplus \phi_x\left(a_{x1}, \dots, a_{xy_x}\right)\right) \ge {1\over2}\sum_{i = 1}^x S(\phi_i).$$Is this true or not? If so, how do we show this? Or does there exist a counterexample?

Improve this question
$\endgroup$
10
  • 4
    $\begingroup$ What is $\oplus$? $\endgroup$
    – fedja
    Commented Mar 26, 2017 at 23:54
  • 2
    $\begingroup$ This does not hold for constant functions. Gerhard "There's A One Gate Minimum" Paseman, 2017.03.26. $\endgroup$
    – Gerhard Paseman
    Commented Mar 27, 2017 at 0:33
  • $\begingroup$ Gerhard, we had the same idea! $\endgroup$
    – Joel David Hamkins
    Commented Mar 27, 2017 at 0:35
  • 1
    $\begingroup$ Why should there be a logical gate for a constant function? It is just like hot/cold wire (so, I would say 0 gates). Of course, it depends on how you count, but let's interpret everything in the favor of the poster. $\endgroup$
    – fedja
    Commented Mar 27, 2017 at 0:45
  • 2
    $\begingroup$ It would not heart if the Author of the Question were more explicit. Nevertheless, it is quite common to define the complexity of a constant as 0. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Mar 27, 2017 at 4:32

3 Answers 3

Reset to default
6
$\begingroup$

EDIT: the strikethroughs are in response to the followup comments that ensued.

I believe this is open. For simplicity, assume the $\phi$'s are the same function. It's a bit more standard to write $L(\phi)$ for the minimum formula size of $\phi$. The original question is whether $L(\oplus_m \circ f) \gtrapprox m L(f)$, where $\oplus_m$ denotes arity-$m$-XOR. Indeed, one could hope even for $L(\oplus_m \circ f) \gtrapprox m^2 L(f)$, since the formula complexity of $\oplus_m$ is $m^2$.

This stronger (potential) lower bound is presented as a major conjecture (Conjecture 1.10) in the following recent work of Gavinsky, Meir, Weinstein, and Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/GavinskyMeWeWi2016.pdf The question dates back to Karchmer-Raz-Wigderson'95.

This leaves open the weaker statement $L(\oplus_m \circ f) \gtrapprox m L(f)$ -- basically, what was asked in the original question -- but my guess is that this is equally unknown.

One more remark: as noted in the paper above, the desired conjecture is true if the XOR operation is replaced by the OR operation.

EDIT: Wegener's observation (see coments) that the desired conjecture holds true for OR seems to apply equally well for XOR, as noted by Fedja. So it would seem that the answer to the poster's question is positive, even without the factor $1/2$, assuming the $\phi$'s are nonconstant.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Hi Ryan, is it possible you could include a proof in the OR case? $\endgroup$
    – user106599
    Commented Mar 27, 2017 at 5:59
  • 1
    $\begingroup$ *Wegener, sorry for the misspelling. It is Theorem 2.1.ii in Section 10.2 of this: eccc.weizmann.ac.il/resources/pdf/cobf.pdf The theorem statement is "S(f v g) = S(f)+S(g)+1, provided f and g are not constant", where f v g means f(x) v g(y), where x and y are disjoint sets of variables. The proof goes like this. Suppose we have a formula for f(x) v g(y) with r leaves. Plug in an input x that makes f = 0. We get a formula for g(y), which must have at least S(g)+1 leaves (by definition), and all these leaves are y-variables. Similarly one can argue that there must be at least.. $\endgroup$
    – Ryan O'Donnell
    Commented Mar 27, 2017 at 13:36
  • 1
    $\begingroup$ .. S(f)+1 many x-variables, by substituting in for y something that makes g = 0. Thus overall there are at least S(f)+S(g)+2 many leaves, implying S(f v g) >= S(f)+S(g)+1. The upper bound is obvious. $\endgroup$
    – Ryan O'Donnell
    Commented Mar 27, 2017 at 13:37
  • 1
    $\begingroup$ @RyanO'Donnell And what's the difference between $\vee$ and $\oplus$ in this proof of the linear bound?. Am I missing something again? $\endgroup$
    – fedja
    Commented Mar 27, 2017 at 15:51
  • 1
    $\begingroup$ Good. It seems the lower bound holds equally well for $\oplus$, therefore answering OP's original question. The upper bound fails to hold, which I guess is what makes the Gavinsky et al. question interesting. $\endgroup$
    – Ryan O'Donnell
    Commented Mar 27, 2017 at 17:22
2
$\begingroup$

Edit As Emil pointed out, that will work for the circuit complexity, but not for the formula complexity. I apologize for being confused, but still will leave this post just as a curious observation.

Here is a possible candidate for an (interesting) counterexample.

Take some big $y$ and a prime $p$ slightly bigger than $2^y$. Let all $\varphi_j$ be the same and return $0$ if the binary number $\overline{a_1\dots a_y}+1$ is a quadratic residue modulo $p$ and $1$ otherwise.

Let $M$ be the complexity of $\varphi$ and $m$ be the complexity of arithmetic operations (addition and multiplication) modulo $p$.

Religious dogma: When $y$ is large, $M/m$ is also large.

If we believe it, then the composite formula can be computed by first multiplying all numbers out, subtracting $1$ and then applying $\varphi$, thus consuming only about $xm+M\ll xM$ gates.

My question is whether we can set up some construction like that staying purely within mathematics.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is a great counterexample. Indeed, iterated multiplication modulo $p$ has polynomial-size formulas (being computable in uniform $\mathrm{TC^0}$), whereas this is very unlikely to be true for the Legendre symbol. $\endgroup$
    – Emil Jeřábek
    Commented Mar 27, 2017 at 10:23
  • $\begingroup$ No, wait a minute. This doesn't work. We are talking formula complexity, not circuit complexity. Thus, the "composite formula" is $\varphi$ with every occurrence of a variable replaced with a separate copy of the appropriate multiplication formula. The total size is roughly the product of the two formula sizes, not their sum. $\endgroup$
    – Emil Jeřábek
    Commented Mar 27, 2017 at 13:10
  • $\begingroup$ @EmilJeřábek What do you mean? Once we have the output of the multiplication ($n$ outgoing wires), we just feed them as inputs of $\varphi$. Also, Legendre symbol is polynomial ($a^{(p-1)/2}\mod p$ computed via the squaring technique), but this requires much more than one multiplication, that's why the dogma. $\endgroup$
    – fedja
    Commented Mar 27, 2017 at 13:52
  • $\begingroup$ Again: these are formulas, not circuits. Each gate can be fed as input to another gate only once. So, each time the output of the multiplication formula is used, it has to be recomputed. Likewise, the Legendre symbol has polynomial circuits, but likely not formulas. A useful equivalent is that a function has poly-size formulas iff it has (bounded fan-in) circuits of logarithmic depth. $\endgroup$
    – Emil Jeřábek
    Commented Mar 27, 2017 at 13:56
  • $\begingroup$ @EmilJeřábek Argh! You don't allow branching wires!!! You are right then. Of course, I thought of circuits rather than formulas. Thanks for the clarification (once I see the word "gate", I immediately think of a circuit somehow). Thanks again! :-) $\endgroup$
    – fedja
    Commented Mar 27, 2017 at 14:34
0
$\begingroup$

I'm not sure what you mean by $\oplus$, but here is a counterexample. Let each $\phi_i(\vec x)$ be a tautology. So $S(\phi_i)=2$. But $\phi_1\oplus\cdots\phi_x$ is also trivial (depending on what you mean by $\oplus$), and so takes just a few operations. But $\frac12\sum_i S(\phi_i)=x$, which can be very large.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .