1
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ Thanks for your replying! It is really helpful. $\endgroup$ – user4565515 May 4 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.