摘要：For a polynomial f, we study the sum of squares representation (SOS), i.e. f = â^'_{i â^^ [s]} c_i f_i² , where c_i are field elements and the f_iâs are polynomials. The size of the representation is the number of monomials that appear across the f_iâs. Its minimum is the support-sum S(f) of f. For simplicity of exposition, we consider univariate f. A trivial lower bound for the support-sum of, a full-support univariate polynomial, f of degree d is S(f) ⥠d^{0.5}. We show that the existence of an explicit polynomial f with support-sum just slightly larger than the trivial bound, that is, S(f) ⥠d^{0.5 ε(d)}, for a sub-constant function ε(d) > Ï(â^S{log log d/log d}), implies that VP â VNP. The latter is a major open problem in algebraic complexity. A further consequence is that blackbox-PIT is in SUBEXP. Note that a random polynomial fulfills the condition, as there we have S(f) = Î~(d). We also consider the sum-of-cubes representation (SOC) of polynomials. In a similar way, we show that here, an explicit hard polynomial even implies that blackbox-PIT is in P.
