Изменения

Рассмотрим язык <tex>S = \{ y | \exists i \in \{0,1\}^{n}: y = E_{i}(0^{m})\}</tex>. Заметим, что этот язык лежит в '''NP'''. Сертификатом для слова <tex>y</tex> является номер <tex>i</tex> шифрующей функции <tex>E_{i}</tex> такой, что <tex>y = E_{i}(0^{m})</tex>. Так как '''NP''' <tex>=</tex> '''P''', то <tex>S</tex> лежит в классе '''P'''. А тогда существует функция <tex>A(y) \in P</tex>, равная нулю, если <tex>y \in S</tex>, и единице в противном случае. Оценим вероятность <tex>P(A(E_{i}(x_{b})) = b)</tex> при <tex>x_{0} = 0^{m}</tex> и некотором <tex>x_{1}</tex>. Заметим, что так как <tex>b</tex> равновероятно может быть и нулем, и единицей, то <tex>P(A(E_{i}(x_{b})) = b) = 0,5 * P(A(E_{i}(x_{0})) = 0) + 0,5 * P(A(E_{i}(x_{1})) = 1)</tex>.