Complexity of minimising polynomial formula size 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. ]
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.