PLS (сложность) - PLS (complexity)

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

Описание

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

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

  • Размер каждого решения полиномиально ограничен размером экземпляра .
  • За полиномиальное время можно найти какое-то решение проблемы.
  • Можно рассчитать стоимость каждого решения за полиномиальное время.
  • Можно найти всех соседей каждого решения за полиномиальное время.

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

Пример

Рассмотрим следующий пример из Макс-2Сат Проблема: . Цель состоит в том, чтобы найти задание, которое максимизирует сумму удовлетворенных пунктов.

А решение для этого экземпляра - это битовая строка, которая присваивает каждому значение 0 или 1. В этом случае решение состоит из 3 бит, например , что означает присвоение к со значением 0. Множество решений это множество всех возможных назначений , и .

В Стоимость каждого решения - это количество удовлетворенных предложений, поэтому потому что второе и третье предложения удовлетворены.

Флип-сосед решения достигается путем переворота одного бита битовой строки , так что соседи находятся со следующими расходами:

Нет соседей с лучшей стоимостью, чем , если мы ищем решение с максимальной стоимостью. Хотя не является глобальным оптимумом (что, например, было бы решением который удовлетворяет всем пунктам и имеет ), является локальным оптимумом, потому что ни у одного из его соседей нет лучших затрат.

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

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

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

Проблема местного поиска имеет набор экземпляров, которые закодированы с использованием струны над конечным алфавит . Для каждого экземпляра существует конечное множество решений . Позволять быть отношением, моделирующим . Соотношение в PLS [2] [3][4] если:

  • Размер каждого решения полиномиально ограничена размером
  • Проблемные экземпляры и решения проверяемы полиномиальным временем
  • Существует функция, вычислимая за полиномиальное время который возвращается для каждого экземпляра какое-то решение
  • Существует функция, вычислимая за полиномиальное время [5] который возвращается для каждого решения экземпляра цена
  • Существует функция, вычислимая за полиномиальное время который возвращает набор соседей для пары экземпляр-решение
  • Существует функция, вычислимая за полиномиальное время который возвращает соседнее решение с лучшей стоимостью, чем решение , или заявляет, что локально оптимален
  • Для каждого случая , точно содержит пары куда является локальным оптимальным решением

Экземпляр имеет структуру неявный граф (также называемый График переходов [6]), вершинами которых являются решения с двумя решениями соединены направленной дугой тогда и только тогда, когда .

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

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

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

  • Подбросить[2] - Соседство решения может быть достигнуто путем инвертирования (переворота) одного произвольного входного бита . Итак, одно решение и все его соседи имеют Расстояние Хэмминга один: .
  • Керниган-Лин[2][6] - Решение является соседом решения если можно получить из последовательностью жадных переворачиваний, при которой ни один бит не переворачивается дважды. Это означает, что начиная с , то Подбросить-сосед из с наилучшей стоимостью или наименьшей потерей стоимости выбирается в качестве соседа s в структуре Керниган-Лин. А также лучший (или наименее худший) сосед и так далее, пока это решение, в котором каждый бит отрицается. Обратите внимание, что нельзя немного перевернуть назад, если он однажды был перевернут.
  • k-переворот[7] - Решение является соседом решения если Расстояние Хэмминга между и самое большее , так .

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

  • Замена[8] - перегородка узлов в графе является соседом раздела если можно получить из поменяв местами один узел с узлом .
  • Керниган-Лин[1][2] - перегородка является соседом если может быть получен жадной последовательностью перестановок из узлов в с узлами в . Это означает, что два узла и меняются местами, где раздел набирает максимально возможный вес или теряет минимально возможный вес. Обратите внимание, что ни один узел не может быть заменен дважды.
  • Фидучча-Матейсес [1][9] - Эта окрестность похожа на структуру соседства Керниган-Лин, это жадная последовательность перестановок, за исключением того, что каждая перестановка происходит в два этапа. Сначала с наибольшим увеличением стоимости или наименьшей потерей стоимости заменяется на , то узел с наибольшей стоимостью или наименьшей потерей стоимости заменяется на чтобы снова уравновесить перегородки. Эксперименты показали, что Fiduccia-Mattheyses имеет меньшее время выполнения на каждой итерации стандартного алгоритма, хотя иногда находит худший локальный оптимум.
  • FM-своп[1] - Эта структура квартала основана на структуре квартала Фидучча-Маттейсес. Каждое решение имеет только одного соседа, раздел, полученный после первого обмена Фидучча-Маттейсес.

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

Рассмотрим следующую вычислительную задачу:Учитывая некоторый пример проблемы PLS , найти локально оптимальное решение такой, что для всех .

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

  1. Использовать найти начальное решение
  2. Использовать алгоритм найти лучшее решение . Если такое решение существует, замените к и повторите шаг 2, иначе вернитесь

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

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

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

Скидки

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

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

Проблема местного поиска PLS-сокращается[2] к проблеме местного поиска если есть две полиномиальные функции времени и такой, что:

  • если это пример , тогда это пример
  • если это решение для из , тогда это решение для из
  • если это местный оптимум, например из , тогда например, должен быть локальным оптимумом из

Достаточно лишь нанести на карту локальные оптимумы к местным оптимумам и сопоставить все другие решения, например, со стандартным решением, возвращаемым .[6]

PLS-скидки переходный.[2]

Жесткое сокращение PLS

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

График переходов[6] экземпляра проблемы ориентированный граф. Узлы представляют собой все элементы конечного множества решений а ребра указывают от одного решения к соседнему со строго лучшей стоимостью. Следовательно, это ациклический граф. Приемник, представляющий собой узел без выходящих ребер, является локальным оптимумом. Высота вершины это длина кратчайшего пути из до ближайшего стока. Высота графа переходов является наибольшей из высот всех вершин, поэтому это высота наибольшего кратчайшего пути от узла до его ближайшего стока.

Определение Плотное сокращение PLS

PLS-сокращение из проблемы местного поиска к проблеме местного поиска этоплотное PLS-сокращение[8] если для любого случая из , подмножество решений, например из можно выбрать так, чтобы выполнялись следующие свойства:

  • содержит, среди прочего, все локальные оптимумы
  • Для любого решения из , решение из можно построить за полиномиальное время, так что
  • Если граф переходов из содержит прямой путь от к , и , но все вершины внутреннего пути находятся вне , то для соответствующих решений и держит либо или же содержит край из к

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

PLS находится между функциональными версиями п и НП: FP ⊆ PLS ⊆ ФНП.[2]

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

Также доказано, что если проблема PLS NP-жесткий, то NP = со-НП.[2]

PLS-полнота

Определение

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

  • находится в PLS
  • каждая проблема в PLS может быть уменьшена до

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

Список неполадок PLS-complete

Это неполный список некоторых известных проблем, завершенных PLS.

Обзор проблем PLS-complete и того, как они сводятся друг к другу. Синтаксис: Оптимизация-проблема / структура соседства. Пунктирная стрелка: PLS-редукция от проблемы к проблеме . Черная стрелка: Плотное PLS-сокращение.[4]

Обозначение: Проблема / Структура соседства

  • Мин. / Макс-контур / Флип оказалось первой проблемой PLS-complete.[2]
  • Положительный-не-все-равно-макс-3 сб. / Флип было доказано, что он является PLS-полным за счет жесткого сокращения PLS от Min / Max-circuit / Flip до Positive-not-all-equal-max-3Sat / Flip. Обратите внимание, что Positive-not-all-equal-max-3Sat / Flip также может быть уменьшено из Max-Cut / Flip.[8]
  • Положительный-не-все-равно-макс-3Сат / Керниган-Лин было доказано, что он является полным PLS с помощью жесткого сокращения PLS от Min / Max-circuit / Flip до Positive-not-all-equal-max-3Sat / Kernighan-Lin.[1]
  • Макс-2Сат /Подбросить было доказано, что он является полным PLS посредством жесткого сокращения PLS от Max-Cut / Flip до Max-2Sat / Flip.[1][8]
  • Мин-4Сб-Б /Подбросить было доказано, что он является PLS-полным за счет жесткого сокращения PLS от Min-circuit / Flip до Min-4Sat-B / Flip.[7]
  • Max-4Sat-B / Flip(или CNF-SAT) было доказано, что он является полным PLS за счет уменьшения PLS от Max-circuit / Flip до Max-4Sat-B / Flip.[12]
  • Max-4Sat- (B = 3) / Флип было доказано, что он является PLS-полным посредством сокращения PLS от Max-circuit / Flip до Max-4Sat- (B = 3) / Flip.[13]
  • Max-Uniform-Graph-Partitioning /Замена было доказано, что он является PLS-полным с помощью жесткого сокращения PLS от Max-Cut / Flip до Max-Uniform-Graph-partitioning / Swap.[8]
  • Max-Uniform-Graph-Partitioning / Фидучча-Матейсес заявлено как PLS-полное без доказательств.[1]
  • Max-Uniform-Graph-Partitioning / FM-своп было доказано, что он является PLS-полным с помощью жесткого сокращения PLS от Max-Cut / Flip до Max-Uniform-Graph-partitioning / FM-Swap.[8]
  • Max-Uniform-Graph-Partitioning / Керниган-Лин было доказано, что он является 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 /Подбросить было доказано, что он является полным PLS за счет жесткого сокращения PLS от Positive-not-all-equal-max-3Sat / Flip до Max-Cut / Flip.[1][8]
  • Max-Cut / Керниган-Лин заявлено как завершенное PLS без доказательств.[6]
  • Min-Independent-Dominating-Set-B / k-Flip было доказано, что он является полным PLS с помощью жесткого сокращения PLS с Min-4Sat-B ’/ Flip до Min-Independent-Dominating-Set-B / k-Flip.[7]
  • Независимый взвешенный набор /Изменять заявлено как завершенное PLS без доказательств.[2][8][6]
  • Максимально-взвешенный-подграф-со-свойством-P / изменение является PLS-полным, если свойство P = "не имеет ребер", так как тогда оно равно Weighted-Independent-Set / Change. Также было доказано, что он является PLS-полным для общего наследственного, нетривиального свойства P посредством жесткого PLS-сокращения от Weighted-Independent-Set / Change до Maximum-Weighted-Subgraph-with-property-P / Change.[14]
  • Комплект-крышка / k-изменение было доказано, что он является PLS-полным для каждого k ≥ 2 посредством жесткого сокращения PLS от (3, 2, r) -Max-Constraint-Assignment / Change до Set-Cover / k-change.[15]
  • Метрика-ТСП / k-Изменить было доказано, что он является полным PLS за счет снижения PLS с Max-4Sat-B / Flip до Metric-TSP / k-Change.[13]
  • Метрика-ТСП / Лин-Керниган было доказано, что он является полным PLS за счет жесткого сокращения PLS от Max-2Sat / Flip до Metric-TSP / Lin-Kernighan.[16]
  • Локальное многопроцессорное планирование / k-изменение было доказано, что он является PLS-полным с помощью жесткого сокращения PLS от Взвешенного-трехмерного-сопоставления / (p, q) -Swap до Local-Multi-Processor-scheduling / (2p + q) -change, где (2p + q ) ≥ 8.[5]
  • Эгоистичное многопроцессорное планирование / k-изменение-со-свойством-t было доказано, что он является PLS-полным с помощью жесткого сокращения PLS от Взвешенного-трехмерного-соответствия / (p, q) -Swap до (2p + q) -Selfish-Multi-Processor-Scheduling / k-change-with-property -t, где (2p + q) ≥ 8.[5]
  • Нахождение чистое равновесие по Нэшу в General-Congestion-Game /Изменять был подтвержден PLS-полным путем жесткого сокращения PLS от Positive-not-all-equal-max-3Sat / Flip до General-Congestion-Game / Change.[17]
  • Нахождение чистое равновесие по Нэшу в Симметричный общий - перегрузка - игра / изменение было доказано, что он является PLS-полным с помощью жесткого сокращения PLS от асимметричного General-Congestion-Game / Change до симметричного General-Congestion-Game / Change.[17]
  • В поисках чистого чистое равновесие по Нэшу в Асимметричная направленная сеть-игры с перегрузкой / изменение было доказано, что PLS-полный за счет жесткого сокращения от Positive-not-all-equal-max-3Sat / Flip до Directed-Network-Congestion-Games / Change [17] а также через резкое сокращение PLS от 2-Threshold-Games / Change до Directed-Network-Congestion-Games / Change.[18]
  • В поисках чистого чистое равновесие по Нэшу в Асимметричные неориентированные сетевые игры с перегрузкой / изменение было доказано, что он завершен PLS с помощью жесткого сокращения PLS от 2-Threshold-Games / Change до Asymmetric Undirected-Network-Congestion-Games / Change.[18]
  • В поисках чистого чистое равновесие по Нэшу в 2-пороговая игра / изменение было доказано, что он является PLS-полным за счет жесткого сокращения от Max-Cut / Flip до 2-Threshold-Game / Change.[18]
  • Нахождение чистое равновесие по Нэшу в Игра по разделению рынка / изменение с полиномиальными ограниченными затратами, как было доказано, является PLS-полным за счет жесткого сокращения PLS от 2-Threshold-Games / Change до Market-Sharing-Game / Change.[18]
  • Нахождение чистое равновесие по Нэшу в Оверлей-Сеть-Дизайн / Изменение было доказано, что он завершен с помощью PLS за счет сокращения с 2-пороговых игр / изменения до наложения-дизайн сети / изменение. Аналогично доказательству асимметричной управляемой сети-перегрузки-игры / изменения, сокращение является жестким.[18]
  • Мин-0-1-Целочисленное программирование / k-переворот было доказано, что он является PLS-полным посредством жесткого сокращения PLS от Min-4Sat-B ’/ Flip до Min-0-1-Integer Programming / k-Flip.[7]
  • Макс-0-1-целочисленное программирование / k-переворот утверждается, что он является PLS-полным из-за сокращения PLS до Max-0-1-Integer Programming / k-Flip, но доказательство опущено.[7]
  • (p, q, r) -Макс-ограничение-присвоение
    • (3, 2, 3) -Max-Constraint-Assignment-3-partite / Change было доказано, что он является PLS-полным посредством жесткого сокращения PLS от Circuit / Flip до (3, 2, 3) -Max-Constraint-Assignment-3-partite / Change.[19]
    • (2, 3, 6) -Max-Constraint-Assignment-2-partite / Change было доказано, что он является PLS-полным с помощью жесткого сокращения PLS от Circuit / Flip до (2, 3, 6) -Max-Constraint-Assignment-2-partite / Change.[19]
    • (6, 2, 2) -Max-Constraint-Assignment / Change было доказано, что он является PLS-полным путем резкого сокращения от Circuit / Flip до (6,2, 2) -Max-Constraint-Assignment / Change.[19]
    • (4, 3, 3) -Max-Constraint-Assignment / Change равно Max-4Sat- (B = 3) / Flip и было доказано, что он является PLS-полным с помощью сокращения PLS из Max-circuit / Flip.[13] Утверждается, что уменьшение может быть увеличено для достижения герметичности.[19]
  • Ближайший-красочный-многогранник / Изменить было доказано, что он является PLS-полным с помощью сокращения PLS от Max-2Sat / Flip до Nearest-Colorful-Polytope / Change.[3]
  • Стабильная конфигурация / флип в Сеть Хопфилда было доказано, что он является PLS-полным, если пороговые значения равны 0, а веса отрицательны, посредством жесткого сокращения PLS от Max-Cut / Flip до Stable-Configuration / Flip.[1][8][16]
  • Взвешенное трехмерное сопоставление / (p, q) -замена было доказано, что он является PLS-полным для p ≥9 и q ≥ 15 посредством жесткого сокращения PLS от (2, 3, r) -Max-Constraint-Assignment-2-partite / Change to Weighted-3Dimensional-Matching / ( p, q) -замены.[5]

Рекомендации

  • Яннакакис, Михалис (2009), «Равновесия, неподвижные точки и классы сложности», Обзор компьютерных наук, 3 (2): 71–85, CiteSeerX  10.1.1.371.5034, Дои:10.1016 / j.cosrev.2009.03.004.
  1. ^ а б c d е ж грамм час я j k л Яннакакис, Михалис (2003). Локальный поиск в комбинаторной оптимизации - Вычислительная сложность. Издательство Принстонского университета. С. 19–55. ISBN  9780691115221.
  2. ^ а б c d е ж грамм час я j k л м п о п Джонсон, Дэвид С; Пападимитриу, Христос Н; Яннакакис, Михалис (1988). «Насколько просто местный поиск?». Журнал компьютерных и системных наук. 37 (1): 79–100. Дои:10.1016/0022-0000(88)90046-3.
  3. ^ а б Мульцер, Вольфганг; Стейн, Янник (10 декабря 2014 г.). "Вычислительные аспекты теоремы Красочного Каратеодори". Дискретная и вычислительная геометрия. 60 (3): 720–755. arXiv:1412.3347. Bibcode:2014arXiv1412.3347M. Дои:10.1007 / s00454-018-9979-у.
  4. ^ а б Борзеховски, Микаэла. «Задачи полиномиального локального поиска (PLS) класса сложности и PLS-полные задачи» (PDF).
  5. ^ а б c d Думрауф, Доминик; Моньен, Буркхард; Тиманн, Карстен (2009). «Многопроцессорное планирование полностью завершено». Системные науки, 2009. HICSS'09. 42-я Гавайская международная конференция по: 1–10.
  6. ^ а б c d е ж грамм Михилс, Уил; Аартс, Эмиль; Корст, Ян (2010). Теоретические аспекты локального поиска. Springer Science & Business Media. ISBN  9783642071485.
  7. ^ а б c d е Клаук, Хартмут (1996). «О жесткости глобального и локального приближения». Труды 5-го скандинавского семинара по теории алгоритмов: 88–99.
  8. ^ а б c d е ж грамм час я Schäffer, Alejandro A .; Яннакакис, Михалис (февраль 1991 г.). «Простые проблемы местного поиска, которые трудно решить». SIAM Журнал по вычислениям. 20 (1): 56–87. Дои:10.1137/0220004.
  9. ^ Fiduccia, C.M .; Маттейс, Р. М. (1982). «Эвристика линейного времени для улучшения сетевых разделов». Материалы 19-й конференции по автоматизации проектирования.: 175–181.
  10. ^ Ангел, Эрик; Кристопулос, Петрос; Зиссимопулос, Василис (2014). Парадигмы комбинаторной оптимизации: проблемы и новые подходы - Локальный поиск: сложность и приближение (2-е изд.). John Wiley & Sons, Inc., Хобокен. С. 435–471. Дои:10.1002 / 9781119005353.ch14. ISBN  9781119005353.
  11. ^ Мегиддо, Нимрод; Пападимитриу, Христос Х (1991). «О тотальных функциях, теоремах существования и вычислительной сложности». Теоретическая информатика. 81 (2): 317–324. Дои:10.1016 / 0304-3975 (91) 90200-Л.
  12. ^ Крентель, М. (1 августа 1990 г.). «О поиске и проверке локально оптимальных решений». SIAM Журнал по вычислениям. 19 (4): 742–749. Дои:10.1137/0219052. ISSN  0097-5397.
  13. ^ а б c Крентель, Марк В. (1989). «Структура в локально оптимальных решениях». Материалы 30-го ежегодного симпозиума по основам компьютерных наук: 216–221.
  14. ^ Симозоно, Шиничи (1997). «Поиск оптимальных подграфов локальным поиском». Теоретическая информатика. 172 (1): 265–271. Дои:10.1016 / S0304-3975 (96) 00135-1.
  15. ^ Думрауф, Доминик; Зюсс, Тим (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.
  16. ^ а б Papadimitriou, C.H .; Schäffer, A. A .; Яннакакис, М. (1990). «О сложности локального поиска». Материалы 22-го симпозиума ACM по теории вычислений: 438–445.
  17. ^ а б c Фабрикант, Алекс; Пападимитриу, Христос; Талвар, Кунал (2004). Сложность чистого равновесия по Нэшу. Труды тридцать шестого ежегодного симпозиума ACM по теории вычислений. ACM. С. 604–612. CiteSeerX  10.1.1.3.7861. Дои:10.1145/1007352.1007445. ISBN  978-1581138528.
  18. ^ а б c d е Аккерманн, Хайнер; Рёглин, Хейко; Фёкинг, Бертольд (2008). «О влиянии комбинаторной структуры на игры с перегрузкой». J. ACM. 55 (6): 25:1–25:22. CiteSeerX  10.1.1.634.4913. Дои:10.1145/1455248.1455249. ISSN  0004-5411.
  19. ^ а б c d Думрауф, Доминик; Моньен, Буркхард (2013). «О PLS-сложности задания максимального ограничения». Теор. Comput. Наука. 469: 24–52. Дои:10.1016 / j.tcs.2012.10.044. ISSN  0304-3975.