Включение P в P/poly. Эффективная система доказательств. Класс NP, примеры. Недетерминированная машина Тюринга, эквивалентные определения класса NP. Сведение по Карпу. NP-полнота задачи об ограниченной остановке.