Системы доказательств и перечислимые языки. Нижняя оценка на палиндром на одноленточной машине. Моделирование машин Тьюринга. Недетерминированные машины Тьюринга. Определения класса NP. Примеры. Сведения по Карпу. Понятние полноты. Полнота задачи об ограниченной остановке. Полнота задачи SAT и 3-SAT.