So I am supposed to give a randomized algorithm that solves a problem with probability
$$q > p \ge {1 \over poly(n)}.$$
I assume that $poly(n)$ means something like $O(n^k)$, but what kind of values does $1/poly(n)$ take then?
So I am supposed to give a randomized algorithm that solves a problem with probability
$$q > p \ge {1 \over poly(n)}.$$
I assume that $poly(n)$ means something like $O(n^k)$, but what kind of values does $1/poly(n)$ take then?
Copyright © 2021 JogjaFile Inc.
You're supposed to give an algorithm such that there exists a polynomial function $f$ such that $p(n)\ge 1/f(n)$ for all $n$?