Вероятностный тест для равенства, оценка \( R^1_{\epsilon}(NE)=O(\log (n/\epsilon)) \). Оценка \( R^1_{\epsilon}(f)>\log C^1(f) \) и как следствие \( R^1_{\epsilon}(NE)>\log n \). Оценка \( R_{\epsilon}(GT)=O(\log^2 n) \). Теорема о связи детерминированной и вероятностной сложности: \( R_{\epsilon}(f)=\Omega(\log C(f)) \). Вероятностные коммуникационные протоколы с общим источником случайности и обозначение \( R^{pub}_{\eps}(f) \). Оценка \( R^{pub,1}_{\epsilon}(NE)=O(-\log \epsilon) \).