Chapter 10: Q11P (page 440)
LetM be a probabilistic polynomial time Turning machine, and let C be a language where for some fixed,
- localid="1657794094101" implies Pr[ M accepts w], localid="1657794117156" and
- localid="1657794100896" implies Pr[ M accepts w] localid="1657794105827" .
- Show that localid="1657794108596" .(Hint: Use the result of Lemma 10.5)
Short Answer
By the weak law of large numbers (or various other bounds from probability theory), there exist k that will make those probabilities on the right as small as desired, and in particular, there exist k that will make them both strictly less than and by using “Amplification lemma” this shows .