Вероятностный тест для равенства, оценка $ 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) $.