Исходные понятия. Длина описания задачи. Кодирование описания. Число бит информации, необходимых для формулировки задачи. Время решения, или число арифметичеких операций, требуемых для решения задачи. Водораздел между полиномиальными и переборными алгоритмами.

Роль задач распознавания в теории алгоритмов. Сводимость оптимизации к распознаванию - почти всегда. Задача о простоте числа. О труднорешаемости задачи разложения на множители составного числа.

Определение классов P и NP. Совпадает ли P с NP или не совпадает - вопрос на миллион долларов. Феноменальный прорыв в изучении труднорешаемых задач в связи с открытием NP-класса.

Машина Тьюринга как универсальный вычислительный прибор. Контраст примитивности устройства с фантастическими возможностями. Тезис Тьюринга. Задача Тьюринга как универсальная переборная (NP-полная) задача.

Джентльменский набор комбинаторных задач. Минимальное остовное дерево (МОД). Задача коммивояжера. Задачи: клика; изоморфизм графов; паросочетание; рюкзак; целочисленное линейное программирование - ЦЛП; транспортная задача. В двух словах (пока) о непрерывной задаче линейного программирования. Логические задача ВЫПОЛНИМОСТЬ.

Теорема Кука устанавливает NP-полноту задачи ВЫПОЛНИМОСТЬ, трансформируя проблематику в область задач, которые можно «пощупать».