<p>You can reduce the co-NP-Complete TAUTOLOGY problem (given a Boolean formula, is it a tautology?) to the problem of minimizing formula size (since a formula is a tautology iff it's equivalent to TRUE). Moreover, TAUTOLOGY for 3DNFs (analogously to SAT for 3CNFs) is co-NP-Complete.</p>

CC BY-SA 3.0
2011-09-14T15:56:29.947Z
I thought about the same approach, but I could not make the degree of the resulting polynomial bounded by a constant.  Is that possible?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-14T15:57:15.843Z
As I understand the question, $f$ should be computed as a polynomial not as a function. Maybe some clarification is needed.
Markus Bläser
CC BY-SA 3.0
2011-09-14T17:31:12.500Z
There is a probabilistic reduction from 3SAT to checking, given a deg-3 polynomial over GF(2), whether it has a zero [by looking at random linear combinations of the clauses], and then from this to checking, given a deg-3 poly over GF(2), whether it is all-zero [by subtracting the poly from 1].
Dana Moshkovitz
CC BY-SA 3.0
2011-09-14T18:50:09.020Z
Thanks! Do you have any idea what the situation is for degree 2 polynomials? Also (though this is probably very dense) I am struggling to see how a degree 3 polynomial over GF(2), written in standard form, can be all-zero without being the zero polynomial. To be clear, I am imagining that the input to my problem is a description of the polynomial itself, rather than a description of a circuit computing the polynomial.
Ashley Montanaro
CC BY-SA 3.0
2011-09-14T21:33:33.947Z
I had been overlooking the random-subset technique.  Thanks for the explanation!
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-15T01:31:04.217Z
1. I'm not sure about the deg-2 case. I would guess that if you think about it for a little and you can't argue it is equivalent to 2SAT, it's probably hard. (I don't have time to think about it now - I have a class to prepare for tomorrow :-)). 2. The polynomial x^2 - x is not identically zero, but it is all-zero over GF(2);
Dana Moshkovitz
CC BY-SA 3.0
2011-09-15T07:01:18.733Z
Thanks again for your reply. I'm still not convinced about the all-zero thing, though; it seems to me that any n-variate polynomial over GF(2) with poly(n) terms can easily be transformed into a standard form where it is obvious whether the polynomial is zero or not, just by making the substitution $x^k \rightarrow x$ and collecting terms.
Ashley Montanaro
CC BY-SA 3.0
2011-09-15T12:17:09.900Z
Indeed if you make it multilinear as you describe, a polynomial evaluates to zero on every input iff it is the zero polynomial. One proof: Select a non-zero monomial M of minimal degree. Set to zero all other variables. The only surviving monomial is M. By setting the vars in M to 1 you get a non-zero output.
Manu
CC BY-SA 3.0
2011-09-17T14:52:29.513Z
The mistake in my argument seems to be that the reduction from Boolean formulas to polynomials inherently produces an ensemble of polynomials, rather than a single polynomial. I'll try to think about the question when I have some more time.
Dana Moshkovitz
CC BY-SA 3.0
2011-09-14T15:48:56.160Z
2011-09-14T15:48:56.160Z
Dana Moshkovitz
<p>Not exactly the answer but hopefully helps:</p>

<p>This question should be  NP hard already for d=2 if you want to know minimal formula for $n$ polynomials and not just for one.
The proof is as following:
There exists one to one correspondence between n bi-linear formulas(formulas of type $\sum a_{ij}x_iy_j$) and 
tensor 3 matrices i.e. elements in $F_2^n\otimes F_2^n\otimes F_2^n $. Such that tensor rank of the matrix is exactly the multiplication complexity of n bi-linear formulas.</p>

<p>It is known that tensor rank $3$ is NP-hard problem(probably approximating tensor rank is also NP-hard). Thus multiplication complexity of $n$ bi-linear formulas is NP-hard problem</p>

CC BY-SA 3.0
2011-09-21T21:33:46.223Z
Thanks! This is an interesting perspective on the problem.
Ashley Montanaro
CC BY-SA 3.0
2011-09-25T03:35:28.167Z
The following theorem helps to pass from many polynomials to one pollynomial: LEt S(f) complexity of one polynomial then complexity of computing all its derivatives is at most 5S(f).  Thus the complexity polynomials $f_1, f_2,\ldots,f_n$ is almost equal to complexity of $z_1f_1+z_2f_2\ldots z_n f_n$
Klim
CC BY-SA 3.0
2011-09-26T13:24:29.227Z
If you talk about tensor rank, then you are only counting multiplications but not additions. The case $d = 2$ and only one bilinear form is easy then, since one can compute the rank of one bilinear form, by using the structure theorems mentioned in Ramprasad's answer. (The proofs of these theorems is algorithmic, see the book by Lidl & Niederreiter.)
Markus Bläser
CC BY-SA 3.0
2011-09-21T17:10:03.737Z
2011-09-21T19:35:05.903Z
2011-09-21T19:35:05.903Z
Klim
<p>Any answer to this depends hugely on the <strong>vocabulary</strong> you allow in the answer.  If you want your answer in the same language as the input (i.e. as a polynomial), that leads to one set of answers, which is what other posters have been struggling with.</p>

<p><strong>But</strong> if you allow your <em>answer vocabulary</em> to be enlarged, wonderful things can happen.  You can see an example in symbolic vs automatic differentiation: in symbolic differentiation one only allows 'expressions', which tend to blow up pretty badly; in automatic differentiation, one allows <em>straight-line programs</em> in the answer (even if the input was an expression), which greatly helps to control the expression swell.  For univariate polynomials, James Davenport and I <a href="http://arxiv.org/abs/1002.0012" rel="nofollow">have mused</a> that you need to throw in cyclotomic polynomials as part of your basic vocabulary as well (see the references as to why these polynomials seem to be the only real source of blow-up, as well as the papers that show various reducibility results between polynomial problems and 3SAT).</p>

<p>In other words, if you allow yourself to vary what you consider an answer a little bit from the classical one, you may just be able to get a rather different answer, i.e. one with a much better complexity.  It depends on your original motivation for asking the question, whether purely theoretical or with an application in mind, to decide whether this variation in vocabulary is acceptable to you.  In the setting where James and I have been thinking about this (symbolic computation), adjusting the vocabulary to make the complexity drop is perfectly acceptable (though seldom done).</p>

CC BY-SA 3.0
2011-09-18T17:06:56.987Z
The question asks for the smallest arithmetic formula, which it then defines clearly. I am therefore not sure this reply is directly relevant. Also, the above answer by Dana Moshkovitz and associated comments don't correctly answer the question as already acknowledged in the comments.
Simd
CC BY-SA 3.0
2011-09-20T00:46:29.003Z
The point of my answer is that the OP might not realize that they are not necessarily asking the best question.  The OP's question is asked in very classical terms, but if you allow a small deviation from that, you get quite different answers, which might have been quite unexpected.  I understand your comment, but feel the downvote is a little harsh.
Jacques Carette
CC BY-SA 3.0
2011-09-20T04:14:33.987Z
Could you correct the first paragraph of your answer to make it clear the question has not been answered correctly yet?   I was worried people might be mislead.
Simd
CC BY-SA 3.0
2011-09-20T12:11:55.363Z
@Raphael: done.  And clarified things further as well.
Jacques Carette
CC BY-SA 3.0
2011-09-18T14:14:36.953Z
2011-09-20T12:11:30.967Z
2011-09-20T12:11:30.967Z
Jacques Carette
<p>The general circuit/formula minimization is certainly harder than identity testing, since the minimum formula size of any identity is simply zero. As for how much harder, I don't have a definitive answer but perhaps the "reconstruction algorithms" studied in arithmetic circuits/formulae might be something along these lines. </p>

<p>In these cases, you are give a blackbox and told that it is a formula in some class $\mathcal{C}$ (say a depth $3$ circuit). The goal is to construct a representation of the blackbox in (something close to) $\mathcal{C}$. Typically, most reconstruction results assume blackbox identity tests for the class, randomness, and sometimes other kinds of queries. Such reconstruction algorithms are available for certain restricted classes of circuits but not all classes for which we know blackbox PITs. Shpilka and Yehudayoff have <a href="http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf" rel="nofollow">a fantastic survey (pdf)</a> on arithmetic circuits, and one of the chapters is entirely on reconstruction algorithms. </p>

<p>But in your case, you say $d$ is a constant and hence even if the input was given as a blackbox, there are reconstruction algorithms for sparse polynomials. So maybe the above comments are not too interesting in this case. </p>

<p>Also, in the case of $d=2$, there are structure theorems for quadratics. Under a linear transformation on the variables, any quadratic can be rewritten in the form $x_1x_2 + x_3x_4 + .. + x_{2k-1}x_{2k} + \ell$. This property was used by Bogdanov and Viola for constructing <a href="http://www.cse.cuhk.edu.hk/~andrejb/pubs/lowdeggen.pdf" rel="nofollow">PRGs for low degree polynomials (pdf)</a> (Lemma 17 of their paper). </p>

CC BY-SA 3.0
2011-09-20T12:33:57.413Z
Thanks for your comments. Sadly, I don't see how to use these ideas to solve the original problem.
Ashley Montanaro
CC BY-SA 3.0
2011-09-20T08:20:20.937Z
2011-09-20T08:30:59.290Z
2011-09-20T08:30:59.290Z
Ramprasad
<p>Let $f(x_1,\dots,x_n)$ be a degree $d$ polynomial in $n$ variables over $\mathbb{F}_2$, where $d$ is constant (say 2 or 3). I would like to find the smallest formula for $f$, where "formula" and "formula size" are defined in the obvious way (eg. the smallest formula for the polynomial $x_1 x_2 + x_1 x_3$ is $x_1(x_2+x_3)$).</p>

<p>What is the complexity of this problem - is it NP-hard? Does the complexity depend on $d$?</p>

<p>[ More formally, a formula (aka "arithmetic formula") is a rooted binary tree, each of whose leaves is labelled with either an input variable or the constant 1. All the other vertices of the tree are labelled with $+$ or $\times$. The size of the formula is the number of leaves used. The formula computes a polynomial recursively: $+$ vertices compute the sum of their children over $\mathbb{F}_2$, $\times$ vertices compute the product. ]</p>

CC BY-SA 3.0
2011-09-13T12:48:46.633Z
can't we reduce polynomial identity testing to this problem?
Kaveh
CC BY-SA 3.0
2011-09-13T13:26:00.550Z
I guess there may be a connection, but I don't immediately see it - in particular because of the constraint on the degree. Besides, if the problem is more difficult than polynomial identity testing, it would be interesting to know how much more difficult.
Ashley Montanaro
CC BY-SA 3.0
2011-09-14T12:49:08.727Z
In your case, how is the number of gates ($+$s, and $\times$s) in the formula related to the actual formula size? For $d=2$, the construction in [Ehrenfeucht and Karpinski 90](http://www.icsi.berkeley.edu/pubs/techreports/tr-90-033.pdf) seems to be relevant (see 2XOR paragraph) for the "gate"-formula size, but I have to think about it longer.
Alessandro Cosentino
CC BY-SA 3.0
2011-09-14T15:10:45.820Z
As the formula is a binary tree, the definition of formula size I've used here (number of leaves) is equal to the number of gates (internal vertices) plus one. But I'd be interested in any results for any other sensible definition of formula size too. I'm not sure I see a connection to the results of Ehrenfeucht and Karpinski, as these are about the complexity of counting solutions, rather than minimising formula size...
Ashley Montanaro
CC BY-SA 3.0
2011-09-14T16:02:17.197Z
In order to count the number of zeros, they first transform the formula to an equivalent one, which I recall being minimum in terms of multiplications and additions. I don't have a proof of this minimality, though. Again, this would answer only the case $d=2$.
Alessandro Cosentino
CC BY-SA 3.0
2011-10-28T14:48:39.373Z
I have asked a related question on [MathOverflow](http://mathoverflow.net/questions/76043/decomposition-of-graphs-as-symmetric-differences-of-copies-of-k-a-b) expressed in terms of graphs. For the case $d = 2$, the two problems have related answers.
Niel de Beaudrap
<cc.complexity-theory><formulas>
Complexity of minimising polynomial formula size
Ashley Montanaro
# Complexity of minimising polynomial formula size

(Asked by: username_0 on 2011-09-13)

Let $f(x\_1,\dots,x\_n)$ be a degree $d$ polynomial in $n$ variables over $\mathbb{F}\_2$, where $d$ is constant (say 2 or 3). I would like to find the smallest formula for $f$, where "formula" and "formula size" are defined in the obvious way (eg. the smallest formula for the polynomial $x\_1 x\_2 + x\_1 x\_3$ is $x\_1(x\_2+x\_3)$).

What is the complexity of this problem - is it NP-hard? Does the complexity depend on $d$?

[ More formally, a formula (aka "arithmetic formula") is a rooted binary tree, each of whose leaves is labelled with either an input variable or the constant 1. All the other vertices of the tree are labelled with $+$ or $\times$. The size of the formula is the number of leaves used. The formula computes a polynomial recursively: $+$ vertices compute the sum of their children over $\mathbb{F}\_2$, $\times$ vertices compute the product. ]

**Tags:** cc.complexity-theory, formulas

> **Comments:**
> **username_1**: can't we reduce polynomial identity testing to this problem?  
> **username_0**: I guess there may be a connection, but I don't immediately see it - in particular because of the constraint on the degree. Besides, if the problem is more difficult than polynomial identity testing, it would be interesting to know how much more difficult.  
> **username_2**: In your case, how is the number of gates ($+$s, and $\times$s) in the formula related to the actual formula size? For $d=2$, the construction in [Ehrenfeucht and Karpinski 90](http://www.icsi.berkeley.edu/pubs/techreports/tr-90-033.pdf) seems to be relevant (see 2XOR paragraph) for the "gate"-formula size, but I have to think about it longer.  
> **username_0**: As the formula is a binary tree, the definition of formula size I've used here (number of leaves) is equal to the number of gates (internal vertices) plus one. But I'd be interested in any results for any other sensible definition of formula size too. I'm not sure I see a connection to the results of Ehrenfeucht and Karpinski, as these are about the complexity of counting solutions, rather than minimising formula size...  
> **username_2**: In order to count the number of zeros, they first transform the formula to an equivalent one, which I recall being minimum in terms of multiplications and additions. I don't have a proof of this minimality, though. Again, this would answer only the case $d=2$.  
> **username_3**: I have asked a related question on [MathOverflow](http://mathoverflow.net/questions/76043/decomposition-of-graphs-as-symmetric-differences-of-copies-of-k-a-b) expressed in terms of graphs. For the case $d = 2$, the two problems have related answers.  

---

## 4 answers

### Answer by username_4 on 2011-09-14. Score: 7

You can reduce the co-NP-Complete TAUTOLOGY problem (given a Boolean formula, is it a tautology?) to the problem of minimizing formula size (since a formula is a tautology iff it's equivalent to TRUE). Moreover, TAUTOLOGY for 3DNFs (analogously to SAT for 3CNFs) is co-NP-Complete.

> **Comments:**
> **username_5**: I thought about the same approach, but I could not make the degree of the resulting polynomial bounded by a constant.  Is that possible?  
> **username_6**: As I understand the question, $f$ should be computed as a polynomial not as a function. Maybe some clarification is needed.  
> **username_4**: There is a probabilistic reduction from 3SAT to checking, given a deg-3 polynomial over GF(2), whether it has a zero [by looking at random linear combinations of the clauses], and then from this to checking, given a deg-3 poly over GF(2), whether it is all-zero [by subtracting the poly from 1].  
> **username_0**: Thanks! Do you have any idea what the situation is for degree 2 polynomials? Also (though this is probably very dense) I am struggling to see how a degree 3 polynomial over GF(2), written in standard form, can be all-zero without being the zero polynomial. To be clear, I am imagining that the input to my problem is a description of the polynomial itself, rather than a description of a circuit computing the polynomial.  
> **username_5**: I had been overlooking the random-subset technique.  Thanks for the explanation!  
> **username_4**: 1. I'm not sure about the deg-2 case. I would guess that if you think about it for a little and you can't argue it is equivalent to 2SAT, it's probably hard. (I don't have time to think about it now - I have a class to prepare for tomorrow :-)). 2. The polynomial x^2 - x is not identically zero, but it is all-zero over GF(2);  
> **username_0**: Thanks again for your reply. I'm still not convinced about the all-zero thing, though; it seems to me that any n-variate polynomial over GF(2) with poly(n) terms can easily be transformed into a standard form where it is obvious whether the polynomial is zero or not, just by making the substitution $x^k \rightarrow x$ and collecting terms.  
> **username_7**: Indeed if you make it multilinear as you describe, a polynomial evaluates to zero on every input iff it is the zero polynomial. One proof: Select a non-zero monomial M of minimal degree. Set to zero all other variables. The only surviving monomial is M. By setting the vars in M to 1 you get a non-zero output.  
> **username_4**: The mistake in my argument seems to be that the reduction from Boolean formulas to polynomials inherently produces an ensemble of polynomials, rather than a single polynomial. I'll try to think about the question when I have some more time.  

---

### Answer by username_8 on 2011-09-21. Score: 4

Not exactly the answer but hopefully helps:

This question should be NP hard already for d=2 if you want to know minimal formula for $n$ polynomials and not just for one.
The proof is as following:
There exists one to one correspondence between n bi-linear formulas(formulas of type $\sum a\_{ij}x\_iy\_j$) and
tensor 3 matrices i.e. elements in $F\_2^n\otimes F\_2^n\otimes F\_2^n $. Such that tensor rank of the matrix is exactly the multiplication complexity of n bi-linear formulas.

It is known that tensor rank $3$ is NP-hard problem(probably approximating tensor rank is also NP-hard). Thus multiplication complexity of $n$ bi-linear formulas is NP-hard problem

> **Comments:**
> **username_0**: Thanks! This is an interesting perspective on the problem.  
> **username_8**: The following theorem helps to pass from many polynomials to one pollynomial: LEt S(f) complexity of one polynomial then complexity of computing all its derivatives is at most 5S(f).  Thus the complexity polynomials $f_1, f_2,\ldots,f_n$ is almost equal to complexity of $z_1f_1+z_2f_2\ldots z_n f_n$  
> **username_6**: If you talk about tensor rank, then you are only counting multiplications but not additions. The case $d = 2$ and only one bilinear form is easy then, since one can compute the rank of one bilinear form, by using the structure theorems mentioned in username_11's answer. (The proofs of these theorems is algorithmic, see the book by Lidl & Niederreiter.)  

---

### Answer by username_9 on 2011-09-18. Score: 2

Any answer to this depends hugely on the **vocabulary** you allow in the answer. If you want your answer in the same language as the input (i.e. as a polynomial), that leads to one set of answers, which is what other posters have been struggling with.

**But** if you allow your *answer vocabulary* to be enlarged, wonderful things can happen. You can see an example in symbolic vs automatic differentiation: in symbolic differentiation one only allows 'expressions', which tend to blow up pretty badly; in automatic differentiation, one allows *straight-line programs* in the answer (even if the input was an expression), which greatly helps to control the expression swell. For univariate polynomials, James Davenport and I [have mused](http://arxiv.org/abs/1002.0012) that you need to throw in cyclotomic polynomials as part of your basic vocabulary as well (see the references as to why these polynomials seem to be the only real source of blow-up, as well as the papers that show various reducibility results between polynomial problems and 3SAT).

In other words, if you allow yourself to vary what you consider an answer a little bit from the classical one, you may just be able to get a rather different answer, i.e. one with a much better complexity. It depends on your original motivation for asking the question, whether purely theoretical or with an application in mind, to decide whether this variation in vocabulary is acceptable to you. In the setting where James and I have been thinking about this (symbolic computation), adjusting the vocabulary to make the complexity drop is perfectly acceptable (though seldom done).

> **Comments:**
> **username_10**: The question asks for the smallest arithmetic formula, which it then defines clearly. I am therefore not sure this reply is directly relevant. Also, the above answer by username_4 and associated comments don't correctly answer the question as already acknowledged in the comments.  
> **username_9**: The point of my answer is that the OP might not realize that they are not necessarily asking the best question.  The OP's question is asked in very classical terms, but if you allow a small deviation from that, you get quite different answers, which might have been quite unexpected.  I understand your comment, but feel the downvote is a little harsh.  
> **username_10**: Could you correct the first paragraph of your answer to make it clear the question has not been answered correctly yet?   I was worried people might be mislead.  
> **username_9**: @Raphael: done.  And clarified things further as well.  

---

### Answer by username_11 on 2011-09-20. Score: 0

The general circuit/formula minimization is certainly harder than identity testing, since the minimum formula size of any identity is simply zero. As for how much harder, I don't have a definitive answer but perhaps the "reconstruction algorithms" studied in arithmetic circuits/formulae might be something along these lines.

In these cases, you are give a blackbox and told that it is a formula in some class $\mathcal{C}$ (say a depth $3$ circuit). The goal is to construct a representation of the blackbox in (something close to) $\mathcal{C}$. Typically, most reconstruction results assume blackbox identity tests for the class, randomness, and sometimes other kinds of queries. Such reconstruction algorithms are available for certain restricted classes of circuits but not all classes for which we know blackbox PITs. Shpilka and Yehudayoff have [a fantastic survey (pdf)](http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf) on arithmetic circuits, and one of the chapters is entirely on reconstruction algorithms.

But in your case, you say $d$ is a constant and hence even if the input was given as a blackbox, there are reconstruction algorithms for sparse polynomials. So maybe the above comments are not too interesting in this case.

Also, in the case of $d=2$, there are structure theorems for quadratics. Under a linear transformation on the variables, any quadratic can be rewritten in the form $x\_1x\_2 + x\_3x\_4 + .. + x\_{2k-1}x\_{2k} + \ell$. This property was used by Bogdanov and Viola for constructing [PRGs for low degree polynomials (pdf)](http://www.cse.cuhk.edu.hk/~andrejb/pubs/lowdeggen.pdf) (Lemma 17 of their paper).

> **Comments:**
> **username_0**: Thanks for your comments. Sadly, I don't see how to use these ideas to solve the original problem.  

---

