Универсальное семейство попарно независимых хеш-функций. Конструкция. Протокол для нижней оценки на размер множества. Публичные и скрытые случайные биты, игры Мерлина и Артура. Классы AM и MA. GNI содержится в AM. Теорема Голдвассера-Сипсера (без доказательства). Из NP-полноты изоморфизма графов следует, что полиномиальная иерархия схлопывается на 2 уровне.