Construire des ensembles de frappes pour des algorithmes randomisés

Question

Supposons un ($ cdot $,$ cdot $) est un algorithme randomisé efficace et l est une langue telle que

$ text {if} x in l, text {pr} _r [(a (x, r) = 1)] = 1 $ et si $ x notin l, text {pr} _r [a (x, r) = 0] ge frac {1} {2} $.

Laisser $ H $ être un jeu de frappe de telle sorte que pour toutes les entrées $ x $ de longueur $ n $, si $ x notin l $, alors $ existe y in h, a (x, y) = 0 $.

Nous devons montrer qu'il existe un ensemble de frappe $ H $ de taille $ O (n) $.

Mon idée est que de la condition $ x notin l, text {pr} _r [a (x, r) = 0] ge frac {1} {2} $, nous pouvons obtenir ça $ x notin l, text {pr} _r [a (x, r) = 1] < frac {1} {2} $. Ensuite, nous pouvons choisir au hasard $ y_1 $, $ y_2 $, ..., $ y_m $ Pour construire un ensemble $ S $. Puis pour toute entrée $ x notin l, pi_ {i = 1} ^ {i = m} pr [a (x, y_i) = 1] <2 ^ {- m} $. Par conséquent, la probabilité qu'il existe au moins une $ y_i $ tel que $ A (x, y_i) = 0 $ est 1 1 - 2 ^ {- m} $. Maintenant, le problème est si nous devons prouver l'ensemble de frappe $ H $ doit exister, alors 1 1 - 2 ^ {- m} $ devrait être 1, ce qui signifie $ m $ devrait être assez grand. Cependant, je ne trouve pas la relation entre $ m $ et $ n $ Et comment se fait-il que $ m $ en taille $ O (n) $ prouverait tel $ y_i $ doit exister.

Ou peut-être que je vais dans le mauvais sens. Quelqu'un peut-il m'aider avec ça? Toute aide serait appréciée. Merci d'avance.