Задачи поиска, сведения, доказательство NP-полноты задач выполнимости, 3-выполнимости, задачи о независимом множестве, задачи о вершинном покрытии.

Литература: [DPV06, глава 8].