Системы доказательств, классы NP и coNP. Пропозициональные системы доказательств. Примеры систем доказательств: таблицы истинностей, деревья решений. Оценки на глубину деревьев решений. Игры Прувера-Делэера. Асимметричные игры Прувера-Делэера и точная оценка на размер дерева решений для принципа Дирихле.

Текущая версия конспекта тут.