Верхняя оценка \(O(1)\) для односторонней вероятностной сложности предиката GT для протоколов с общими случайными битами. Оценка \(O(\log^2 n)\) вероятностной двусторонней сложности предиката GT. Оценка \(O(\log n)\) для односторонней сложности предиката GT для протоколов с общими случайными битами.

Амплификация.

Теорема Ньюмана об уменьшении количества случайных битов и замене общих битов на приватные.