This thesis settles a number of questions related to computational complexity and algebraic, semidefinite programming based relaxations in optimization and control.