Costruire set di colpi per algoritmi randomizzati

Question

Supponiamo a ($ CDOT $,$ CDOT $) è un algoritmo randomizzato efficiente e L è un linguaggio tale che

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

Permettere $ H $ essere un set di colpi in modo tale che per tutti gli input $ x $ di lunghezza $ n $, Se $ x notin l $, poi $ esiste y in h, a (x, y) = 0 $.

Dobbiamo dimostrare che esiste un set da colpire $ H $ di dimensioni $ O (n) $.

La mia idea è che dalla condizione $ x notin l, text {pr} _r [a (x, r) = 0] ge frac {1} {2} $, possiamo ottenerlo $ x notin l, text {pr} _r [a (x, r) = 1] < frac {1} {2} $. Allora possiamo scegliere casualmente $ y_1 $, $ y_2 $, ..., $ y_m $ Per costruire un set $ S $. Quindi per qualsiasi input $ x notin l, pi_ {i = 1}^{i = m} pr [a (x, y_i) = 1] <2^{-m} $. Pertanto, la probabilità che esista almeno uno $ y_i $ tale che $ A (x, y_i) = 0 $ è $ 1 - 2^{ - m} $. Ora il problema è se dobbiamo dimostrare il set di colpi $ H $ deve esistere, quindi $ 1 - 2^{ - m} $ dovrebbe essere 1, il che significa $ m $ dovrebbe essere abbastanza grande. Tuttavia, non riesco a trovare la relazione tra $ m $ e $ n $ E come mai se $ m $ di dimensioni di $ O (n) $ si dimostrerebbe $ y_i $ deve esistere.

O forse vado nel modo sbagliato. Qualcuno può aiutarmi con questo? Qualsiasi aiuto sarebbe apprezzato. Grazie in anticipo.