NP-полнота задачи Circuit-SAT и задачи о независимом множестве. NP-задачи поиска. Сведения по Тьюрингу. Сведение задач поиска к задачам распознавания. Теорема Ладнера.