In this paper we introduce a new type of probabilistic search algorithm, which we call the{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,and to produce a correct and {\it unique} solution with high probability.We argue the applicability of such algorithms forthe problems of verifying delegated computation in a distributed setting, and for generatingcryptographic public-parameters and keys in distributed settings.We exhibit several examples of Bellagio algorithms for problemsfor which no deterministic polynomial time algorithms are known.In particular,we show such algorithms for:\begin{itemize}\item finding a unique generatorfor \Z\ when p is a prime of the form kq+1 for q is prime and k=\polylog(p).The algorithm runs in expected polynomial in logp time.\item finding aunique q'th non-residues of \Z\ for any prime divisor q of p−1,extending Lenstra's \cite{L} algorithm for finding unique quadratic non-residue of \Z.The algorithm runs in expected polynomial time in logp and q.The tool we use is a new variant of the Adleman-Manders-Miller probabilistic algorithm fortaking q-th roots, which outputs a uniquesolution to the input equations and runs in expected polynomial time inlogp and q.\item given a multi-variate polynomial P=0 , find a unique (with high probability) a such thatP(a)=0 . Alternatively you may think of this as producing a unique polynomial timeverifiable certificate of inequality of polynomials.\end{itemize}

More generally, we show a necessary and sufficient condition for the existence ofa Bellagio Algorithm for relation R: R has a Bellagio algorithm if and onlyif it is deterministically reducible to some decision problem in BPP