Определение класса NP, примеры. Доказательство простоты числа (критерий Пратта). Сведения и полнота. NP-полнота задачи об ограниченной остановке. Сведение Circuit-SAT к 3SAT.