$NP$-задачи поиска. Сведения по Куку. Сведение задач поиска к задачам распознавания. Оптимальный алгоритм для $NP$-задач поиска. Класс $PSPACE$ и полная задача в нем. Теорема Ладнера о не $NP$-полном языке в классе $NP$.