Машины Тьюринга. Моделирование машин Тьюринга схемами. NP-полнота задачи Circuit-SAT. Деревья поиска противоречия. Нижняя оценка на принцип Дирихле с помощью игр. Резолюционные доказательства и их связь с деревьями поиска противоречия.