Ефикасни алгоритми и алгоритмична неподатливост.
Двата вида неподатливост според Garey & Johnson.

Задачите за разпознаване като формални езици.
Кодирания и разумни кодирания.  Езикът, съответен
на задача за разпознаване и нейно кодиране.

Детерминирана машина на Тюринг (МТ).  Конфигурация
на МТ.  Приемаща и отхвърляща конфигурация.

Езикът, разпознаван от МТ.  Решаване на задача за разпознаване от
машина на Тюринг

Машини на Тюринг–изчислители на стрингови функции.  Композиция на
машини на Тюринг–изчислители на стрингови функции.

Сложност по време на МТ.  Клас на сложност P.

Недетерминирани машини на Тюринг (НМТ).  Двете алтернативни
дефиниции НМТ: машини с размножаване и машини-верификатори.
Кратка аргументация за еквивалентността на тези варианти на НМТ.

Как приема и как отхвърля НМТ.

Езикът, разпознаван от НМТ.  Решаване на задача за разпознаване от НМТ.

Сложност по време на НМТ. Клас на сложност NP.

Защо P е подмножество на NP.

Karp редукции между задачи и Karp редукции между езици.

<=p като релация.  Свойства на тази релация: рефлексивност
и транзитивност.  Доказателство на транзитивност (Теорема 128).

Полиномиална еквивалентност между задачи за разпознаване.
Полиномиална несравнимост на задачи за разпознаване.
Кога задача за разпознаване е полиномиално строго по-малка от друга задача
за разпознаване.

Класът P и полиномиалните редукции (Теорема 129).

Теорема 130: P е минималният клас на еквивалентност на релацията <=p .

Клас на сложност NP-c (Определение 142).

Определение 143: Клас на сложност NP-h.