На прошлой лекции мы увидели простой параллельный алгоритм для проверки, существует ли в графе совершенное паросочетание. В нём использовалась лемма Шварца-Зиппеля о том, что подставляя случайные числа в полином от нескольких переменных, с малой вероятностью мы наткнёмся на корень полинома. В этой лекции докажем лемму Шварца-Ципля.

Когда хочется не только понять, существует ли оно, но также вычислить его, то нужно гарантировать, чтобы все процессора вычисляли одно и то же паросочетание, а не разные. Для этого мы познакомимся с совершенно удивительной изоляционной леммой. Она говорит о том, что если мы рассматриваем семейство множеств над общим носителем и каждому элементу носителя выдадим случайный вес, то с высокой вероятностью в семействе множеств есть одно единственное множество минимального веса.

Изоляционная лемма также имеет последствия для теории сложности вычислений --- теорема Валианта-Варизани. Она говорит о том, что для эффективного решения NP-полных задач рандомизированными алгоритмами достаточно уметь их эффективно решать под предположением, что для них существует одно единственное решение.