Связь вероятностной и детерминированной сложностей. Нижняя оценка вероятностной сложности предиката EQ.

Нижние оценки двусторонней вероятностной сложности с помощью распределений вероятностей на входах. Теорема Фон-Ноймана и универсальность этого метода.

Пестрота. Нижняя оценка двусторонней вероятностной сложности предиката скалярного произведения с помощью пестроты.