Связь безошибочной вероятностной, односторонней вероятностной и недетерминированной сложностей. Вероятностный безошибочный протокол для DISJ$_{nk}$ и пример квадратичного разрыва между детерминированной и вероятностной безошибочной сложностями.