Given a polynomial $p \in \mathbb{R}[x_1, \ldots, x_n]$, suppose that for each monomial in $p$, $c_\alpha x_1^{\alpha_1} \ldots x_n^{\alpha_n}$ we have $\alpha_i = 0, 1, 2$. I have been calling these polynomials multiquadratic (is there another established name for them?).

I am interested in developing an algorithm to decide if given a multiquadratic polynomial $p$ it is positive semidefinite, that is if for all inputs in $\mathbf{x} \in \mathbb{R}^n$ we have $p(\mathbf{x}) \geq 0$. In general I have been told this is a difficult problem unless one can reduce to sum of squares which is not always possible.

In the case of multiquadratic polynomials are all positive semidefinite polynomials sum of squares?

**Edit: I believe the polynomial $p(x,y,z) = x^2y^2 + x^2 z^2 + y^2 z^2 - 4xyz + 1$ is PSD, multiquadratic, but not SOS**

**Is there still a decent algorithm for determining if a given multiquadratic polynomial is PSD? Is this a NP-hard problem?**