Is it possible to solve the n-variable, degree-d SOS relaxation in n^{O(d)} time?  I don't know.  Approximately?  I don't know.  In the Archimedean case?  I don't know. 
  What about telling whether a multivariate polynomial with rational coefficients is a sum of squares: is this in P?  I don't know.  Is it in NP?  I don't know.  Is it in PSPACE?  Yes, although it's nontrivial.
  I'll discuss some of these issues, including recent positive results.