Обзор результатов, связанных с нахождением локальных оптимумов в задачах комбинаторной оптимизации. Рассматривается класс задач локального поиска (класс PLS) и по аналогии с теоремой Кука устанавливается существование наиболее сложных задач в этом классе. Приводятся оценки числа шагов алгоритмов локального спуска в худшем и среднем случаях. Обсуждаются возможности получения локальным поиском точных и приближенных решений с гарантированными оценками точности.
