# Constructing hitting sets for randomized algorithms

Suppose A($$\cdot$$,$$\cdot$$) is an efficient randomized algorithm and L is a language such that

$$\text{If }x \in L, \text{Pr}_r[(A(x,r) = 1)] = 1$$ and if $$x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \frac{1}{2}$$.

Let $$H$$ be a hitting set such that for all inputs $$x$$ of length $$n$$, if $$x \notin L$$, then $$\exists y \in H, A(x, y) = 0$$.

We need to show that there exists a hitting set $$H$$ of size $$O(n)$$.

My idea is that from the condition $$x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \frac{1}{2}$$, we can get that $$x \notin L, \text{Pr}_r[A(x, r) = 1] < \frac{1}{2}$$. Then we can randomly choose $$y_1$$, $$y_2$$, ..., $$y_m$$ to construct a set $$S$$. Then for any input $$x \notin L, \Pi_{i = 1}^{i = m}Pr[A(x, y_i) = 1] < 2^{-m}$$. Therefore, the probability that there exists at least one $$y_i$$ such that $$A(x, y_i) = 0$$ is $$1 - 2^{-m}$$. Now the problem is if we need to prove the hitting set $$H$$ must exist, then $$1 - 2^{-m}$$ should be 1, which means $$m$$ should be large enough. However, I cannot find the relationship between $$m$$ and $$n$$ and how come if $$m$$ in size of $$O(n)$$ would prove such $$y_i$$ must exist.

Or maybe I am going in the wrong way. Can somebody help me with this? Any help would be appreciated. Thanks in advance.

• What's the distribution for $r$ when you say $\mathrm{Pr}_r$? Note there is no uniform distribution over the set of all strings. – xskxzr May 3 at 6:26

Suppose that $$H$$ consists of $$m$$ seeds chosen uniformly at random (thus $$|H|$$ could be smaller than $$m$$). For each $$x \notin L$$, the probability that $$A(x,r) = 1$$ for all $$r \in H$$ is at most $$2^{-m}$$. Since there are at most $$2^n$$ inputs of length $$n$$ not in $$L$$, we get that the probability that $$H$$ is not a hitting set is at most $$2^n/2^m$$. Choosing $$m = n+1$$, we see that the probability that $$H$$ is not a hitting set is at most $$1/2$$, and in particular there must exist a hitting set of size at most $$n+1$$. If $$L \cap \Sigma^n \neq \emptyset$$, we can improve this to $$m = n$$.