  We consider nondeterministic probabilistic programs with the most basic
liveness property of termination. We present efficient methods for termination
analysis of nondeterministic probabilistic programs with polynomial guards and
assignments. Our approach is through synthesis of polynomial ranking
supermartingales, that on one hand significantly generalizes linear ranking
supermartingales and on the other hand is a counterpart of polynomial
ranking-functions for proving termination of nonprobabilistic programs. The
approach synthesizes polynomial ranking-supermartingales through
Positivstellensatz's, yielding an efficient method which is not only sound, but
also semi-complete over a large subclass of programs. We show experimental
results to demonstrate that our approach can handle several classical programs
with complex polynomial guards and assignments, and can synthesize efficient
quadratic ranking-supermartingales when a linear one does not exist even for
simple affine programs.
