Пожалуйста (сложность)

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

Описание

При поиске локального оптимума приходится решать два интересных вопроса: во-первых, как найти локальный оптимум, и, во-вторых, сколько времени потребуется, чтобы найти локальный оптимум. Для многих алгоритмов локального поиска неизвестно, смогут ли они найти локальный оптимум за полиномиальное время или нет. ^[1] Итак, чтобы ответить на вопрос, сколько времени потребуется, чтобы найти локальный оптимум, Джонсон, Пападимитриу и Яннакакис ^[2] представили класс сложности PLS в своей статье «Насколько прост локальный поиск?». Он содержит задачи локального поиска, для которых локальная оптимальность может быть проверена за полиномиальное время.

Проблема локального поиска возникает в PLS, если выполняются следующие свойства:

Размер каждого решения полиномиально ограничен размером экземпляра. $I$ .
Некоторое решение конкретной задачи можно найти за полиномиальное время.
Стоимость каждого решения можно рассчитать за полиномиальное время.
Всех соседей каждого решения можно найти за полиномиальное время.

Зная эти свойства, можно для каждого решения найти $s$ лучшее соседнее решение или, если такого лучшего соседнего решения не существует, укажите, что $s$ является локальным оптимумом.

Пример

Рассмотрим следующий пример $I$ проблемы Max-2Sat : $(x_{1}\vee x_{2})\wedge (\neg x_{1}\vee x_{3})\wedge (\neg x_{2}\vee x_{3})$ . Цель состоит в том, чтобы найти задание, которое максимизирует сумму выполненных предложений.

Решение $s$ для этого экземпляра — это битовая строка, которая присваивает каждому $x_{i}$ значение 0 или 1. В этом случае решение состоит из 3 бит, например $s=000$ , что означает присвоение $x_{1}$ к $x_{3}$ со значением 0. Множество решений $F_{L}(I)$ представляет собой множество всех возможных присвоений $x_{1}$ , $x_{2}$ и $x_{3}$ .

Стоимость каждого решения равна числу удовлетворенных предложений, поэтому $c_{L}(I,s=000)=2$ потому что второе и третье предложение выполнены.

Флип- сосед решения $s$ достигается путем переворота одного бита битовой строки $s$ , поэтому соседи $s$ являются $N(I,000)=\{100,010,001\}$ со следующими затратами:

$c_{L}(I,100)=2$

$c_{L}(I,010)=2$

$c_{L}(I,001)=2$

Нет соседей с лучшими ценами, чем $s$ , если мы ищем решение с максимальной стоимостью. Несмотря на то $s$ не является глобальным оптимумом (который, например, был бы решением $s'=111$ который удовлетворяет всем пунктам и имеет $c_{L}(I,s')=3$ ), $s$ является локальным оптимумом, поскольку ни у одного из его соседей затраты не выше.

Интуитивно можно утверждать, что эта проблема кроется в PLS , потому что:

Можно найти решение экземпляра за полиномиальное время, например, установив все биты в 0.
Стоимость решения можно рассчитать за полиномиальное время, пройдя один раз весь экземпляр и подсчитав удовлетворенные условия.
Можно найти всех соседей решения за полиномиальное время, взяв набор решений, отличающихся от $s$ ровно в одном бите.

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

Формальное определение

Проблема с локальным поиском $L$ есть набор $D_{L}$ экземпляров, которые закодированы с использованием строк в конечном алфавите $\Sigma$ . Для каждого экземпляра $I$ существует конечное множество решений $F_{L}(I)$ . Позволять $R$ быть отношением, которое моделирует $L$ . Отношение $R\subseteq D_{L}\times F_{L}(I):=\{(I,s)\mid I\in D_{L},s\in F_{L}(I)\}$ есть в пожалуйста ^[2]^[3]^[4] если:

Размер каждого решения $s\in F_{L}(I)$ полиномиально ограничен по размеру $I$
Проблемные случаи $I\in D_{L}$ и решения $s\in F_{L}(I)$ проверяемы за полиномиальное время
Существует полиномиально вычислимая функция $A:D_{L}\rightarrow F_{L}(I)$ который возвращается для каждого экземпляра $I\in D_{L}$ какое-то решение $s\in F_{L}(I)$
Существует полиномиально вычислимая функция $B:D_{L}\times F_{L}(I)\rightarrow \mathbb {R} ^{+}$ ^[5] который возвращается для каждого решения $s\in F_{L}(I)$ экземпляра $I\in D_{L}$ стоимость $c_{L}(I,s)$
Существует полиномиально вычислимая функция $N:D_{L}\times F_{L}(I)\rightarrow Powerset(F_{L}(I))$ который возвращает набор соседей для пары экземпляр-решение
Существует полиномиально вычислимая функция $C:D_{L}\times F_{L}(I)\rightarrow N(I,s)\cup \{OPT\}$ который возвращает соседнее решение $s'$ с более выгодной стоимостью, чем решение $s$ или заявляет, что $s$ является локально оптимальным
Для каждого экземпляра $I\in D_{L}$ , $R$ точно содержит пары $(I,s)$ где $s$ является локальным оптимальным решением $I$

Экземпляр $D_{L}$ имеет структуру неявного графа (также называемого графом переходов ^[6]), вершины являются решениями с двумя решениями $s,s'\in F_{L}(I)$ соединены направленной дугой тогда и только тогда, когда $s'\in N(I,s)$ .

Локальный оптимум – это решение $s$ , у которого нет соседа с лучшими ценами. В неявном графе локальный оптимум является стоком. Окрестность, в которой каждый локальный оптимум является глобальным оптимумом , то есть решением с наилучшей возможной стоимостью, называется точной окрестностью . ^[6]^[1]

Альтернативное определение

Класс PLS — это класс, содержащий все задачи, которые можно за полиномиальное время свести к задаче Sink-of- DAG. ^[7] (также называемый Local-Opt ^[8]): Даны два целых числа $n$ и $m$ и две логические схемы $S:\{0,1\}^{n}\rightarrow \{0,1\}^{n}$ такой, что $S(0^{n})\neq 0^{n}$ и $V:\{0,1\}^{n}\rightarrow \{0,1,..,2^{m}-1\}$ , найти вершину $x\in \{0,1\}^{n}$ такой, что $S(x)\neq x$ и либо $S(S(x))=S(x)$ или $V(S(x))\leq V(x)$ .

Примеры соседских структур

Примеры структур окрестностей для задач с логическими переменными (или битовыми строками) в качестве решения:

Подбросить ^[2] - Окрестность решения $s=x_{1},...,x_{n}$ может быть достигнуто путем отрицания (переворота) одного произвольного входного бита $x_{i}$ . Итак, одно решение $s$ и все его соседи $r\in N(I,s)$ единице расстояние Хэмминга равно : $H(s,r)=1$ .
Керниган-Лин ^[2]^[6] - Решение $r$ является соседом решения $s$ если $r$ можно получить из $s$ с помощью последовательности жадных переворотов, при которой ни один бит не переворачивается дважды. Это значит, начиная с $s$ , Flip -сосед $s_{1}$ из $s$ с лучшей стоимостью или наименьшей потерей стоимости выбирается соседом s в структуре Кернигана-Лина. А также лучший (или наименее худший) сосед $s_{1}$ и так далее, пока $s_{i}$ это решение, в котором каждый бит $s$ отрицается. Обратите внимание, что его нельзя перевернуть немного назад, если он уже был однажды перевернут.
k-флип ^[9] - Решение $r$ является соседом решения $s$ если расстояние Хэмминга $H$ между $s$ и $r$ самое большее $k$ , так $H(s,r)\leq k$ .

Примеры структур окрестностей для задач на графах:

Менять ^[10] - Перегородка $(P_{2},P_{3})$ узлов в графе является соседом раздела $(P_{0},P_{1})$ если $(P_{2},P_{3})$ можно получить из $(P_{0},P_{1})$ путем замены одного узла $p_{0}\in P_{0}$ с узлом $p_{1}\in P_{1}$ .
Керниган-Лин ^[1]^[2] - Перегородка $(P_{2},P_{3})$ является соседом $(P_{0},P_{1})$ если $(P_{2},P_{3})$ может быть получен жадной последовательностью перестановок узлов в $P_{0}$ с узлами в $P_{1}$ . Это означает, что два узла $p_{0}\in P_{0}$ и $p_{1}\in P_{1}$ меняются местами, где раздел $((P_{0}\setminus p_{0})\cup p1,(P_{1}\setminus p_{1})\cup p_{0})$ набирает максимально возможный вес или теряет минимально возможный вес. Обратите внимание, что ни один узел не может быть заменен дважды.
Фидучча-Матейсес ^[1]^[11] - Эта окрестность аналогична структуре окрестностей Кернигана-Лина, это жадная последовательность обменов, за исключением того, что каждый обмен происходит в два этапа. Сначала $p_{0}\in P_{0}$ с наибольшим выигрышем в стоимости или наименьшей потерей стоимости, заменяется на $P_{1}$ , то узел $p_{1}\in P_{1}$ с наибольшей стоимостью или наименьшей потерей стоимости заменяется на $P_{0}$ чтобы снова сбалансировать разделы. Эксперименты показали, что Фидучча-Маттейзес имеет меньшее время выполнения на каждой итерации стандартного алгоритма, хотя иногда он находит худший локальный оптимум.
FM-замена ^[1] - Эта структура соседства основана на структуре соседства Фидуччиа-Маттейсеса. Каждое решение $s=(P_{0},P_{1})$ имеет только одного соседа — раздел, полученный после первого обмена Фидуччиа-Маттейс.

Стандартный алгоритм

Рассмотрим следующую вычислительную задачу: Учитывая некоторый пример $I$ о проблеме с PLS $L$ , найти локально оптимальное решение $s\in F_{L}(I)$ такой, что $c_{L}(I,s')\geq c_{L}(I,s)$ для всех $s'\in N(I,s)$ .

Любую задачу локального поиска можно решить, используя следующий алгоритм итеративного улучшения: ^[2]

Использовать $A_{L}$ найти первоначальное решение $s$
Использовать алгоритм $C_{L}$ чтобы найти лучшее решение $s'\in N(I,s)$ . Если такое решение существует, замените $s$ к $s'$ и повторите шаг 2, иначе вернитесь $s$

К сожалению, обычно требуется экспоненциальное количество шагов по улучшению, чтобы найти локальный оптимум, даже если проблема $L$ может быть решена точно за полиномиальное время. ^[2] Не обязательно всегда использовать стандартный алгоритм, для определенной задачи может существовать другой, более быстрый алгоритм. Например, алгоритм локального поиска, используемый для линейного программирования, — это симплексный алгоритм .

Время работы стандартного алгоритма псевдополиномиально от числа различных стоимостей решения. ^[12]

Пространство, необходимое стандартному алгоритму, является только полиномиальным. Нужно только сохранить текущее решение $s$ , который по определению является полиномиально ограниченным. ^[1]

Скидки

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

PLS-сокращение

Проблема с локальным поиском $L_{1}$ является PLS-редуцируемым ^[2] к проблеме локального поиска $L_{2}$ если существуют две полиномиальные функции времени $f:D_{1}\rightarrow D_{2}$ и $g:D_{1}\times F_{2}(f(I_{1}))\rightarrow F_{1}(I_{1})$ такой, что:

если $I_{1}$ является примером $L_{1}$ , затем $f(I_{1})$ является примером $L_{2}$
если $s_{2}$ это решение для $f(I_{1})$ из $L_{2}$ , затем $g(I_{1},s_{2})$ это решение для $I_{1}$ из $L_{1}$
если $s_{2}$ является локальным оптимумом, например $f(I_{1})$ из $L_{2}$ , затем $g(I_{1},s_{2})$ например, должен быть локальный оптимум $I_{1}$ из $L_{1}$

Достаточно лишь отобразить локальные оптимумы $f(I_{1})$ к локальному оптимуму $I_{1}$ и сопоставить все остальные решения, например, со стандартным решением, возвращаемым $A_{1}$ . ^[6]

PLS-редукции транзитивны . ^[2]

Плотное PLS-снижение

Определение Граф перехода

Граф перехода ^[6] $T_{I}$ экземпляра $I$ проблемы $L$ представляет собой ориентированный граф. Узлы представляют все элементы конечного множества решений. $F_{L}(I)$ а ребра указывают от одного решения к соседнему со строго лучшей стоимостью. Следовательно, это ациклический граф. Приемник, представляющий собой узел без выходящих ребер, является локальным оптимумом. Высота вершины $v$ длина кратчайшего пути из $v$ до ближайшей мойки. Высота графа переходов — это наибольшая из высот всех вершин, то есть это высота наибольшего кратчайшего пути от узла до его ближайшего стока.

Определение: Плотное PLS-уменьшение

PLS-сокращение $(f,g)$ из-за проблемы локального поиска $L_{1}$ к проблеме локального поиска $L_{2}$ это жесткое PLS-сокращение ^[10] если для любого случая $I_{1}$ из $L_{1}$ , подмножество $R$ решений например $I_{2}=f(I_{1})$ из $L_{2}$ можно выбрать так, чтобы удовлетворялись следующие свойства:

$R$ содержит, среди прочих решений, все локальные оптимумы $I_{2}$
Для каждого решения $p$ из $I_{1}$ , решение $q\in R$ из $I_{2}=f(I_{1})$ можно построить за полиномиальное время, так что $g(I_{1},q)=p$
Если граф перехода $T_{f(I_{1})}$ из $f(I_{1})$ содержит прямой путь от $q$ к $q_{0}$ , и $q,q_{0}\in R$ , но все вершины внутреннего пути находятся снаружи $R$ , то для соответствующих решений $p=g(I_{1},q)$ и $p_{0}=g(I_{1},q_{0})$ имеет либо $p=p_{0}$ или $T_{I_{1}}$ содержит ребро из $p$ к $p_{0}$

Связь с другими классами сложности

PLS находится между функциональными версиями P и NP : FP ⊆ PLS ⊆ FNP . ^[2]

PLS также является подклассом TFNP . ^[13] который описывает вычислительные задачи, в которых решение гарантированно существует и может быть распознано за полиномиальное время. Для задачи в PLS гарантированно существует решение, поскольку вершина всего графа с минимальной стоимостью является допустимым решением, а достоверность решения можно проверить, вычислив ее соседей и сравнив стоимости каждого из них с другим.

Также доказано, что если задача PLS NP-трудна , то NP = co-NP . ^[2]

PLS-полнота

Определение

Проблема с локальным поиском $L$ является PLS-полным, ^[2] если

$L$ есть в пожалуйста
любую проблему в PLS можно свести к $L$

оптимизационная версия задачи схемы в рамках структуры окрестности Флипа является первой PLS-полной задачей. Было показано, что ^[2]

Список PLS-полных проблем

Это неполный список некоторых известных проблем, которые являются PLS-полными. Проблемы здесь — взвешенные версии; например, Max-2SAT/Flip является взвешенным, хотя Max-2SAT обычно относится к невзвешенной версии.

Обозначение: Задача/Структура окрестности.

Min/Max-circuit/Flip является первой PLS-полной задачей. Было доказано, что ^[2]
Sink-of -DAG является полным по определению.
Положительный-не все-равен-макс-3Sat/Flip» Доказано, что « является PLS-полным посредством жесткого PLS-сокращения от Min/Max-circuit/Flip до «Positive-not-all-equal-max-3Sat/Flip». Обратите внимание, что значение Positive-not-all-equal-max-3Sat/Flip также можно уменьшить по сравнению с Max-Cut/Flip. ^[10]
Positive-not-all-equal-max-3Sat/Kernighan-Lin Было доказано, что является PLS-полным посредством жесткого PLS-сокращения от Min/Max-circuit/Flip до Positive-not-all-equal-max-3Sat/ Керниган-Лин. ^[1]
Max-2Sat /Flip является PLS-полным благодаря жесткому PLS-сокращению от Max-Cut/Flip до Max-2Sat/Flip. Было доказано, что ^[1]^[10]
Min-4Sat-B /Flip является PLS-полным благодаря жесткому PLS-сокращению от Min-circuit/Flip до Min-4Sat-B/Flip. Было доказано, что ^[9]
Max-4Sat-B/Flip (или CNF-SAT) является PLS-полным за счет PLS-сокращения от Max-circuit/Flip до Max-4Sat-B/Flip. Было доказано, что ^[14]
Max-4Sat-(B=3)/Flip является PLS-полным посредством PLS-редукции от Max-circuit/Flip до Max-4Sat-(B=3)/Flip. Было доказано, что ^[15]
Max-Uniform-Graph-Partitioning /Swap является PLS-полным благодаря жесткому PLS-сокращению от Max-Cut/Flip до Max-Uniform-Graph-partitioning/Swap. Было доказано, что ^[10]
Без доказательства утверждается, что Max-Uniform-Graph-Partitioning /Fiduccia-Matheyses является PLS-полным. ^[1]
Max-Uniform-Graph-Partitioning /FM-Swap является PLS-полным благодаря жесткому PLS-сокращению от Max-Cut/Flip до Max-Uniform-Graph-partitioning/FM-Swap. Было доказано, что ^[10]
Max-Uniform-Graph-Partitioning /Kernighan-Lin является PLS-полным посредством PLS-сокращения от Min/Max-circuit/Flip до Max-Uniform-Graph-Partitioning/Kernighan-Lin. Было доказано, что ^[2] Существует также жесткое сокращение PLS от Positive-not-all-equal-max-3Sat/Kernighan-Lin до Max-Uniform-Graph-Partitioning/Kernighan-Lin. ^[1]
Max-Cut /Flip является PLS-полным благодаря жесткому PLS-сокращению от Positive-not-all-equal-max-3Sat/Flip до Max-Cut/Flip. Было доказано, что ^[1]^[10]
Утверждается, что Max-Cut /Kernighan-Lin является PLS-полным без каких-либо доказательств. ^[6]
Min-Independent-Dominating-Set-B/k-Flip Было доказано, что является PLS-полным посредством жесткого PLS-сокращения от Min-4Sat-B ′ /Flip до Min-Independent-Dominating-Set-B/k-Flip. . ^[9]
Утверждается, что Weighted-Independent-Set /Change является PLS-полным без каких-либо доказательств. ^[2]^[10]^[6]
Максимально-взвешенный-подграф-с-свойством-P/Change является PLS-полным, если свойство P = «не имеет ребер», поскольку тогда оно равно Weighted-Independent-Set/Change. Также было доказано, что он является PLS-полным для общего наследственного нетривиального свойства P посредством жесткой PLS-редукции от взвешенного независимого набора/изменения к максимально взвешенному подграфу со свойством P/изменение. ^[16]
Set-Cover /k-change Было доказано, что является PLS-полным для каждого k ≥ 2 посредством жесткого PLS-сокращения от (3, 2, r)-Max-Constraint-Assignment/Change до Set-Cover/k-change. . ^[17]
Metric-TSP /k-Change является PLS-полным посредством PLS-сокращения от Max-4Sat-B/Flip до Metric-TSP/k-Change. Было доказано, что ^[15]
Metric-TSP /Lin-Kernighan является PLS-полным благодаря жесткому сокращению PLS от Max-2Sat/Flip до Metric-TSP/Lin-Kernighan. Было доказано, что ^[18]
Доказано, что локальное многопроцессорное планирование /k-change является PLS-полным посредством жесткого PLS-сокращения от взвешенного трехмерного соответствия/(p, q)-Swap к локальному многопроцессорному планированию/(2p +q)-замена, где (2p + q) ≥ 8. ^[5]
эгоистичное многопроцессорное планирование/k-изменение со свойством-t Доказано, что является PLS-полным благодаря жесткому PLS-сокращению от взвешенного трехмерного сопоставления/(p, q)-замены до (2p+q) )-Эгоистичное-многопроцессорное планирование/k-изменение-со-свойством-t, где (2p + q) ≥ 8. ^[5]
Нахождение чистого равновесия Нэша в игре с общей перегрузкой /изменением было доказано завершенным PLS посредством жесткого PLS-редукции от «Положительное-не-все-равно-максимум-3 сат/переворот» к «Игра с общей перегрузкой/изменением». ^[19]
Было доказано, что поиск чистого равновесия Нэша в симметричной игре с общей перегрузкой/изменением является PLS-полным за счет жесткой PLS-редукции от асимметричной игры с общей перегрузкой/изменением к симметричной игре/изменению с общей перегрузкой. ^[19]
Было доказано, что поиск чистого равновесия Нэша в асимметричных играх с направленной перегрузкой сети/изменением является PLS-полным за счет резкого сокращения от «Положительное-не-все-равно-максимум-3 сат/переворот» до направленной-перегруженности сети- Игры/Изменения ^[19] а также посредством жесткого сокращения PLS с 2-пороговых игр/изменения до игр с направленной перегрузкой сети/изменения. ^[20]
Было доказано, что поиск чистого равновесия Нэша в асимметричных ненаправленных сетевых играх с перегрузкой/изменением является PLS-полным за счет жесткого PLS-сокращения от 2-пороговых игр/изменений к асимметричным ненаправленным сетевым играм с перегрузкой/изменением. . ^[20]
поиск чистого равновесия Нэша в симметричных играх с перегрузкой сети, ограниченной расстоянием, является PLS-полным благодаря жесткому PLS-редукции от игр с 2 порогами к играм с симметричной сетью, ограниченной расстоянием. Было доказано, что ^[21]
Было доказано, что поиск чистого равновесия Нэша в двухпороговой игре/изменении является PLS-завершенным благодаря резкому сокращению от максимального сокращения/переворота до двухпороговой игры/изменения. ^[20]
Было доказано, что поиск чистого равновесия Нэша в игре/изменении с разделением рынка с полиномиальными ограниченными издержками является PLS-полным за счет жесткого PLS-сокращения от 2-пороговых игр/изменения к игре/изменениям с разделением рынка. ^[20]
Было доказано, что поиск чистого равновесия Нэша в схеме «Наложение-Сетевое проектирование/Изменение» является PLS-завершенным за счет сокращения от 2-пороговых игр/Изменения к Наложению-Сетевое проектирование/Изменение. Аналогично доказательству асимметричной игры «Направленная сеть-перегрузка-изменение» редукция является жесткой. ^[20]
Min-0-1-Integer Programming /k-Flip Было доказано, что является PLS-полным благодаря жесткому PLS-сокращению от Min-4Sat-B ′ /Flip до Min-0-1-Integer Programming/k-Flip. ^[9]
Программирование Max-0-1-Integer /k-Flip считается PLS-полным из-за PLS-редукции до Max-0-1-Integer Programming/k-Flip, но доказательство не учитывается. ^[9]
(p, q, r)-Макс-ограничение-назначение
- Доказано, что (3, 2, 3)-Max-Constraint-Assignment-3-partite/Change является PLS-полным благодаря жесткому PLS-редуцированию от Circuit/Flip до (3, 2, 3)-Max-Constraint- Назначение-3-частное/Изменить. ^[22]
- Доказано, что (2, 3, 6)-Max-Constraint-Assignment-2-partite/Change является PLS-полным благодаря жесткому PLS-редуцированию от Circuit/Flip до (2, 3, 6)-Max-Constraint- Назначение-2-частное/Изменение. ^[22]
- Доказано, что (6, 2, 2)-Max-Constraint-Assignment/Change является PLS-полным благодаря жесткому сокращению от Circuit/Flip до (6,2, 2)-Max-Constraint-Assignment/Change. ^[22]
- (4, 3, 3)-Max-Constraint-Assignment/Change равен Max-4Sat-(B=3)/Flip и, как было доказано, является PLS-полным посредством PLS-сокращения от Max-circuit/Flip. ^[15] Утверждается, что сокращение можно продлить, чтобы обеспечить герметичность. ^[22]
ближайший цветной многогранник/изменение является PLS-полным посредством PLS-редукции от Max-2Sat/Flip до ближайшего цветного многогранника/изменения. Доказано, что ^[3]
Stable-Configuration/Flip в сети Хопфилда является PLS-полной, если пороговые значения равны 0, а веса отрицательны, посредством жесткого PLS-сокращения от Max-Cut/Flip до Stable-Configuration/Flip. Было доказано, что ^[1]^[10]^[18]
взвешенное трехмерное сопоставление /(p, q)-Swap Доказано, что является PLS-полным для p ≥9 и q ≥ 15 посредством жесткого PLS-сокращения из (2, 3, r)-Max-Constraint-Assignment- 2-частичное/переход на взвешенное-3-мерное сопоставление/(p, q)-замена. ^[5]
Задача Real-Local-Opt (нахождение локального оптимума λ-липшицевой непрерывной целевой функции) $V:[0,1]^{3}\rightarrow [0,1]$ и функция соседства $S:[0,1]^{3}\rightarrow [0,1]^{3}$ ) является PLS-полным. ^[8]
Было доказано, что обнаружение локального пика приспособленности в ландшафтах биологической приспособленности , заданных NK-моделью / точечной мутацией с K ≥ 2, является PLS-полным посредством жесткого PLS-редукции от Max-2SAT/Flip. ^[23]

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

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

Дальнейшее чтение

Равновесия, фиксированные точки и классы сложности: обзор. ^[25]

Ссылки

Яннакакис, Михалис (2009), «Равновесия, фиксированные точки и классы сложности», Computer Science Review , 3 (2): 71–85, CiteSeerX 10.1.1.371.5034 , doi : 10.1016/j.cosrev.2009.03.004 .

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Яннакакис, Михалис (2003). Локальный поиск в комбинаторной оптимизации — Вычислительная сложность . Издательство Принстонского университета. стр. 19–55. ISBN 9780691115221 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п Джонсон, Дэвид С; Пападимитриу, Христос Х; Яннакакис, Михалис (1988). «Насколько прост локальный поиск?» . Журнал компьютерных и системных наук . 37 (1): 79–100. дои : 10.1016/0022-0000(88)90046-3 .
^ Jump up to: ^а ^б Мюльцер, Вольфганг; Штейн, Янник (14 марта 2018 г.). «Вычислительные аспекты красочной теоремы Каратеодори». Дискретная и вычислительная геометрия . 60 (3): 720–755. arXiv : 1412.3347 . Бибкод : 2014arXiv1412.3347M . дои : 10.1007/s00454-018-9979-y . S2CID 254024141 .
^ Jump up to: ^а ^б Боржеховский, Микаэла. «Класс сложности полиномиального локального поиска (PLS) и PLS-полные задачи» (PDF) .
^ Jump up to: ^а ^б ^с ^д Думрауф, Доминик; Моньен, Буркхард; Тиманн, Карстен (2009). «Многопроцессорное планирование является завершенным PLS» . Системные науки, 2009. HICSS'09. 42-я Гавайская международная конференция : 1–10.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Михилс, Уил; Аартс, Эмиль; Корст, Ян (2010). Теоретические аспекты локального поиска . Springer Science & Business Media. ISBN 9783642071485 .
^ Фернли, Джон; Гордон, Спенсер; Мехта, Рута; Савани, Рахул (декабрь 2020 г.). «Уникальный конец потенциальной линии» . Журнал компьютерных и системных наук . 114 : 1–35. arXiv : 1811.03841 . дои : 10.1016/j.jcss.2020.05.007 .
^ Jump up to: ^а ^б Даскалакис, Константинос; Пападимитриу, Христос (23 января 2011 г.). «Непрерывный локальный поиск». Труды двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 790–804. дои : 10.1137/1.9781611973082.62 . ISBN 978-0-89871-993-2 . S2CID 2056144 .
^ Jump up to: ^а ^б ^с ^д ^и Клаук, Хартмут (1996). «О сложности глобальной и локальной аппроксимации» . Труды 5-го скандинавского семинара по теории алгоритмов : 88–99.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Шеффер, Алехандро А.; Яннакакис, Михалис (февраль 1991 г.). «Простые проблемы локального поиска, которые трудно решить». SIAM Journal по вычислительной технике . 20 (1): 56–87. дои : 10.1137/0220004 .
^ Фидучча, CM; Маттейсес, РМ (1982). «Эвристика линейного времени для улучшения сетевых разделов» . Материалы 19-й конференции по автоматизации проектирования : 175–181. ISBN 9780897910200 .
^ Ангел, Эрик; Христопулос, Петрос; Зиссимопулос, Василис (2014). Парадигмы комбинаторной оптимизации: проблемы и новые подходы - Локальный поиск: сложность и аппроксимация (2-е изд.). John Wiley & Sons, Inc., Хобокен. стр. 435–471. дои : 10.1002/9781119005353.ch14 . ISBN 9781119005353 .
^ Мегиддо, Нимрод; Пападимитриу, Христос Х (1991). «О полных функциях, теоремах существования и вычислительной сложности» . Теоретическая информатика . 81 (2): 317–324. CiteSeerX 10.1.1.75.4797 . дои : 10.1016/0304-3975(91)90200-Л .
^ Крентель, М. (1 августа 1990 г.). «О поиске и проверке локально оптимальных решений». SIAM Journal по вычислительной технике . 19 (4): 742–749. дои : 10.1137/0219052 . ISSN 0097-5397 .
^ Jump up to: ^а ^б ^с Крентель, Марк В. (1989). «Структура в локально оптимальных решениях» . 30-й ежегодный симпозиум по основам информатики . стр. 216–221. дои : 10.1109/SFCS.1989.63481 . ISBN 0-8186-1982-1 . S2CID 32686790 .
^ Симозоно, Шиничи (1997). «Нахождение оптимальных подграфов локальным поиском» . Теоретическая информатика . 172 (1): 265–271. дои : 10.1016/S0304-3975(96)00135-1 .
^ Думрауф, Доминик; Зюсс, Тим (2010). «О сложности локального поиска задач взвешенного стандартного набора». CiE 2010: Программы, доказательства, процессы . Конспекты лекций по информатике. Том. 6158. Шпрингер, Берлин, Гейдельберг. стр. 132–140. CiteSeerX 10.1.1.762.6801 . дои : 10.1007/978-3-642-13962-8_15 . ISBN 978-3-642-13961-1 . S2CID 14099014 .
^ Jump up to: ^а ^б Пападимитриу, Швейцария; Шеффер, А.А.; Яннакакис, М. (1990). «О сложности локального поиска» . Материалы двадцать второго ежегодного симпозиума ACM по теории вычислений - STOC '90 . стр. 438–445. дои : 10.1145/100216.100274 . ISBN 0897913612 . S2CID 16877206 .
^ Jump up to: ^а ^б ^с Фабрикант, Алекс; Пападимитриу, Христос; Талвар, Кунал (2004). «Сложность чистых равновесий Нэша». Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений . АКМ. стр. 604–612. CiteSeerX 10.1.1.3.7861 . дои : 10.1145/1007352.1007445 . ISBN 978-1581138528 . S2CID 1037326 .
^ Jump up to: ^а ^б ^с ^д ^и Аккерманн, Хайнер; Реглин, Хайко; Фёкинг, Бертольд (2008). «О влиянии комбинаторной структуры на игры с перегрузкой». Дж. АКМ . 55 (6): 25:1–25:22. CiteSeerX 10.1.1.634.4913 . дои : 10.1145/1455248.1455249 . ISSN 0004-5411 . S2CID 3070710 .
^ Ян, Ичен; Цзя, Кай; Ринар, Мартин (2022). «О влиянии способностей игроков на игры с перегрузками» . Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 13584. стр. 311–328. arXiv : 2205.09905 . дои : 10.1007/978-3-031-15714-1_18 . ISBN 978-3-031-15713-4 .
^ Jump up to: ^а ^б ^с ^д Думрауф, Доминик; Моньен, Буркхард (2013). «О PLS-сложности назначения максимальных ограничений» . Теор. Вычислить. Наука . 469 : 24–52. дои : 10.1016/j.tcs.2012.10.044 . ISSN 0304-3975 .
^ Казначеев, Артем (2019). «Вычислительная сложность как окончательное ограничение эволюции» . Генетика . 212 (1): 245–265. doi : 10.1534/genetics.119.302000 . ПМК 6499524 . ПМИД 30833289 .
^ Фернли, Джон; Гольдберг, Пол; Холлендер, Александрос; Савани, Рахул (19 декабря 2022 г.). «Сложность градиентного спуска: CLS = PPAD ∩ PLS» . Журнал АКМ . 70 (1): 7:1–7:74. arXiv : 2011.01929 . дои : 10.1145/3568163 . ISSN 0004-5411 . S2CID 263706261 .
^ Яннакакис, Михалис (1 мая 2009 г.). «Равновесия, неподвижные точки и классы сложности» . Обзор компьютерных наук . 3 (2): 71–85. arXiv : 0802.2831 . дои : 10.1016/j.cosrev.2009.03.004 . ISSN 1574-0137 .

[Yan88-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л Яннакакис, Михалис (2003). Локальный поиск в комбинаторной оптимизации — Вычислительная сложность . Издательство Принстонского университета. стр. 19–55. ISBN 9780691115221 .

[JPY88-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п Джонсон, Дэвид С; Пападимитриу, Христос Х; Яннакакис, Михалис (1988). «Насколько прост локальный поиск?» . Журнал компьютерных и системных наук . 37 (1): 79–100. дои : 10.1016/0022-0000(88)90046-3 .

[MS14-3] Jump up to: ^а ^б Мюльцер, Вольфганг; Штейн, Янник (14 марта 2018 г.). «Вычислительные аспекты красочной теоремы Каратеодори». Дискретная и вычислительная геометрия . 60 (3): 720–755. arXiv : 1412.3347 . Бибкод : 2014arXiv1412.3347M . дои : 10.1007/s00454-018-9979-y . S2CID 254024141 .

[Bor16-4] Jump up to: ^а ^б Боржеховский, Микаэла. «Класс сложности полиномиального локального поиска (PLS) и PLS-полные задачи» (PDF) .

[DMT09-5] Jump up to: ^а ^б ^с ^д Думрауф, Доминик; Моньен, Буркхард; Тиманн, Карстен (2009). «Многопроцессорное планирование является завершенным PLS» . Системные науки, 2009. HICSS'09. 42-я Гавайская международная конференция : 1–10.

[MAK07-6] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Михилс, Уил; Аартс, Эмиль; Корст, Ян (2010). Теоретические аспекты локального поиска . Springer Science & Business Media. ISBN 9783642071485 .

[Fea+20-7] Фернли, Джон; Гордон, Спенсер; Мехта, Рута; Савани, Рахул (декабрь 2020 г.). «Уникальный конец потенциальной линии» . Журнал компьютерных и системных наук . 114 : 1–35. arXiv : 1811.03841 . дои : 10.1016/j.jcss.2020.05.007 .

[DP11-8] Jump up to: ^а ^б Даскалакис, Константинос; Пападимитриу, Христос (23 января 2011 г.). «Непрерывный локальный поиск». Труды двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 790–804. дои : 10.1137/1.9781611973082.62 . ISBN 978-0-89871-993-2 . S2CID 2056144 .

[Kla96-9] Jump up to: ^а ^б ^с ^д ^и Клаук, Хартмут (1996). «О сложности глобальной и локальной аппроксимации» . Труды 5-го скандинавского семинара по теории алгоритмов : 88–99.

[SY91-10] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Шеффер, Алехандро А.; Яннакакис, Михалис (февраль 1991 г.). «Простые проблемы локального поиска, которые трудно решить». SIAM Journal по вычислительной технике . 20 (1): 56–87. дои : 10.1137/0220004 .

[FM82-11] Фидучча, CM; Маттейсес, РМ (1982). «Эвристика линейного времени для улучшения сетевых разделов» . Материалы 19-й конференции по автоматизации проектирования : 175–181. ISBN 9780897910200 .

[ACZ14-12] Ангел, Эрик; Христопулос, Петрос; Зиссимопулос, Василис (2014). Парадигмы комбинаторной оптимизации: проблемы и новые подходы - Локальный поиск: сложность и аппроксимация (2-е изд.). John Wiley & Sons, Inc., Хобокен. стр. 435–471. дои : 10.1002/9781119005353.ch14 . ISBN 9781119005353 .

[MP91-13] Мегиддо, Нимрод; Пападимитриу, Христос Х (1991). «О полных функциях, теоремах существования и вычислительной сложности» . Теоретическая информатика . 81 (2): 317–324. CiteSeerX 10.1.1.75.4797 . дои : 10.1016/0304-3975(91)90200-Л .

[Kre90-14] Крентель, М. (1 августа 1990 г.). «О поиске и проверке локально оптимальных решений». SIAM Journal по вычислительной технике . 19 (4): 742–749. дои : 10.1137/0219052 . ISSN 0097-5397 .

[Kre89-15] Jump up to: ^а ^б ^с Крентель, Марк В. (1989). «Структура в локально оптимальных решениях» . 30-й ежегодный симпозиум по основам информатики . стр. 216–221. дои : 10.1109/SFCS.1989.63481 . ISBN 0-8186-1982-1 . S2CID 32686790 .

[Shi97-16] Симозоно, Шиничи (1997). «Нахождение оптимальных подграфов локальным поиском» . Теоретическая информатика . 172 (1): 265–271. дои : 10.1016/S0304-3975(96)00135-1 .

[DS10-17] Думрауф, Доминик; Зюсс, Тим (2010). «О сложности локального поиска задач взвешенного стандартного набора». CiE 2010: Программы, доказательства, процессы . Конспекты лекций по информатике. Том. 6158. Шпрингер, Берлин, Гейдельберг. стр. 132–140. CiteSeerX 10.1.1.762.6801 . дои : 10.1007/978-3-642-13962-8_15 . ISBN 978-3-642-13961-1 . S2CID 14099014 .

[PSY90-18] Jump up to: ^а ^б Пападимитриу, Швейцария; Шеффер, А.А.; Яннакакис, М. (1990). «О сложности локального поиска» . Материалы двадцать второго ежегодного симпозиума ACM по теории вычислений - STOC '90 . стр. 438–445. дои : 10.1145/100216.100274 . ISBN 0897913612 . S2CID 16877206 .

[FPT04-19] Jump up to: ^а ^б ^с Фабрикант, Алекс; Пападимитриу, Христос; Талвар, Кунал (2004). «Сложность чистых равновесий Нэша». Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений . АКМ. стр. 604–612. CiteSeerX 10.1.1.3.7861 . дои : 10.1145/1007352.1007445 . ISBN 978-1581138528 . S2CID 1037326 .

[ARV08-20] Jump up to: ^а ^б ^с ^д ^и Аккерманн, Хайнер; Реглин, Хайко; Фёкинг, Бертольд (2008). «О влиянии комбинаторной структуры на игры с перегрузкой». Дж. АКМ . 55 (6): 25:1–25:22. CiteSeerX 10.1.1.634.4913 . дои : 10.1145/1455248.1455249 . ISSN 0004-5411 . S2CID 3070710 .

[YJR22-21] Ян, Ичен; Цзя, Кай; Ринар, Мартин (2022). «О влиянии способностей игроков на игры с перегрузками» . Алгоритмическая теория игр . Конспекты лекций по информатике. Том. 13584. стр. 311–328. arXiv : 2205.09905 . дои : 10.1007/978-3-031-15714-1_18 . ISBN 978-3-031-15713-4 .

[DM13-22] Jump up to: ^а ^б ^с ^д Думрауф, Доминик; Моньен, Буркхард (2013). «О PLS-сложности назначения максимальных ограничений» . Теор. Вычислить. Наука . 469 : 24–52. дои : 10.1016/j.tcs.2012.10.044 . ISSN 0304-3975 .

[Kaznatcheev-23] Казначеев, Артем (2019). «Вычислительная сложность как окончательное ограничение эволюции» . Генетика . 212 (1): 245–265. doi : 10.1534/genetics.119.302000 . ПМК 6499524 . ПМИД 30833289 .

[24] Фернли, Джон; Гольдберг, Пол; Холлендер, Александрос; Савани, Рахул (19 декабря 2022 г.). «Сложность градиентного спуска: CLS = PPAD ∩ PLS» . Журнал АКМ . 70 (1): 7:1–7:74. arXiv : 2011.01929 . дои : 10.1145/3568163 . ISSN 0004-5411 . S2CID 263706261 .

[25] Яннакакис, Михалис (1 мая 2009 г.). «Равновесия, неподвижные точки и классы сложности» . Обзор компьютерных наук . 3 (2): 71–85. arXiv : 0802.2831 . дои : 10.1016/j.cosrev.2009.03.004 . ISSN 1574-0137 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]