An $n$-variate polynomial of degree 4 can have exponentially many local minima. Indeed, they can be "written down" as solutions of the the corresponding systems of cubic equations, but this doesn't really help you to find a global minimum. 

<b>Edit</b>: e.g. take $f(x_1,\dots x_n)=\sum_{k=1}^n (1-x_k^2)^2.$ Then the minima of $f$ are in the points $(\pm 1,\dots,\pm 1)$.