Попарно-независимые хеш-функции. Лемма Вэлианта-Вазирани. Вычисления с ограничениями и по времени, и по памяти. Нижняя оценка для SAT.