  We consider the problem of finding exact sums of squares (SOS) decompositions
for certain classes of non-negative multivariate polynomials, relying on
semidefinite programming (SDP) solvers.
  We start by providing a hybrid numeric-symbolic algorithm computing exact
rational SOS decompositions for polynomials lying in the interior of the SOS
cone. It computes an approximate SOS decomposition for a perturbation of the
input polynomial with an arbitrary-precision SDP solver. An exact SOS
decomposition is obtained thanks to the perturbation terms. We prove that bit
complexity estimates on output size and runtime are both polynomial in the
degree of the input polynomial and simply exponential in the number of
variables. Next, we apply this algorithm to compute exact Polya and Putinar's
representations respectively for positive definite forms and positive
polynomials over basic compact semi-algebraic sets. We also compare the
implementation of our algorithms with existing methods in computer algebra
including cylindrical algebraic decomposition and critical point method.
