Complexity Aspects of Fundamental Questions in Polynomial Optimization