Введение

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

Сокращения

Приведение одной задачи к другой может быть использовано для демонстрации того, что вторая задача не проще первой. В частности, PLS-приведение используется для доказательства того, что задача локального поиска, принадлежащая классу PLS, также является PLS-полной, путем сведения PLS-полной задачи к той, для которой требуется доказать PLS-полноту.

Отношение к другим классам сложности

PLS лежит между функциональными классами P и NP: FP ⊆ PLS ⊆ FNP. Он описывает вычислительные задачи, в которых гарантированно существует решение, и его можно проверить за полиномиальное время. Для задачи из PLS гарантировано существование решения, поскольку вершина с минимальной стоимостью во всем графе является допустимым решением, а правильность решения можно проверить, вычислив её соседей и сравнив стоимость каждого из них с другими. Также доказано, что если задача PLS является NP-трудной, то NP = coNP.

Отношения с другими классами сложности

Фернли, Голдберг, Холлендер и Савани доказали, что класс сложности CLS равен пересечению классов PPAD и PLS.