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