Теоремы классификации Макс/мин CSP/Единицы

В теории сложности вычислений , разделе информатики , теоремы классификации Max/min CSP/Ones устанавливают необходимые и достаточные условия, которые определяют классы сложности задач об удовлетворении подмножества S логических отношений. ^[1] Они подобны теореме дихотомии Шефера , которая классифицирует сложность удовлетворения конечных наборов отношений; однако теоремы классификации Max/min CSP/Ones дают информацию о сложности аппроксимации оптимального решения проблемы, определяемой S .

Учитывая набор S предложений, проблема удовлетворения ограничений Max (CSP) состоит в том, чтобы найти максимальное количество (в взвешенном случае: максимальную сумму весов) выполнимых предложений в S . Аналогично, задача Min CSP состоит в том, чтобы минимизировать количество невыполненных условий. Задача Max Ones состоит в том, чтобы максимизировать количество логических переменных в S , которым присвоено значение 1 при условии, что все условия выполняются, а проблема Min Ones состоит в том, чтобы минимизировать это число. ^[2]

При использовании приведенной ниже классификации класс сложности задачи определяется самой верхней классификацией, которой она удовлетворяет .

Определения

Здесь для краткости мы определим некоторые термины, которые используются в приведенной ниже классификации.

PO означает полиномиальную оптимизацию по времени; задачи, для которых поиск оптимума может быть выполнен за полиномиальное время, так что аппроксимация с произвольной точностью также явно может быть выполнена за полиномиальное время.
Конъюнктивная нормальная форма сокращенно обозначается CNF . ниже
X(N)OR-SAT обозначает проблему выполнимости, которая представляет собой операцию AND нескольких логических линейных уравнений, которые можно записать в виде предложений XOR. Ровно один литерал в каждом предложении XOR должен быть отрицательным (например, $x_{1}\oplus \lnot x_{2}\oplus x_{3}=1$ ). См. XOR-SAT .
Min UnCut-complete относится к классу сложности, исторически определенному в терминах задачи под названием Min UnCut. Такие задачи являются APX-сложными, но с $O({\sqrt {\log n}})$ факторная аппроксимация. ^[3]
Min 2CNF-Deletion-complete — еще один класс сложности, исторически определяемый с помощью проблемы. Такие задачи являются APX-сложными, но с $O({\sqrt {\log n}})$ приближение. ^[3]
Nearest Codeword-complete — еще один такой класс сложности. Такие задачи не могут быть решены с точностью до $2^{\log ^{1-\epsilon }(n)}$ фактор для некоторых $\epsilon$ .
Min Horn-Deletion-complete — еще один такой класс сложности. Такие задачи не могут быть решены с точностью до $2^{\log ^{1-\epsilon }(n)}$ фактор для некоторых $\epsilon$ , но находятся в Poly-APX, поэтому имеют некоторую полиномиальную аппроксимацию.

Классификационные теоремы

Макс. CSP

Следующие условия составляют классификационную теорему для задач Max CSP. ^[1]

Если установка всех переменных true или всех переменных false удовлетворяет всем условиям, это находится в PO.
Если все предложения при преобразовании в дизъюнктивную нормальную форму имеют два термина: один состоит из всех положительных (неотрицаемых) переменных, а другой - из всех отрицательных переменных, то это находится в PO.
В противном случае проблема APX-полная .

Макс Уанс

Следующие условия составляют классификационную теорему для задач Max Ones. ^[1]

Если установка всех переменных true удовлетворяет всем условиям, это находится в PO.
Если каждое предложение может быть записано как CNF подпунктов Dual-Horn , оно находится в PO.
Если это экземпляр 2-X(N)OR-SAT, то есть X(N)OR-SAT с двумя переменными на линейное уравнение, то он находится в PO.
Если это экземпляр X(N)OR-SAT, но не 2-X(N)OR-SAT, он APX-полный.
Если каждое предложение может быть записано как CNF подпунктов Horn , оно является Poly-APX-полным .
Если это экземпляр 2-CNF-SAT , он является Poly-APX-полным.
Если установка всех или всех переменных, кроме одной, false удовлетворяет каждому предложению, это Poly-APX-полная.
NP -трудно отличить ответ 0 от ненулевого ответа, если установка всех переменных ложью удовлетворяет всем условиям.
В противном случае найти хотя бы допустимое решение будет NP-трудно.

Минимальный CSP

Следующие условия составляют классификационную теорему для задач Min CSP. ^[1]

Если установка всех переменных false или true всех переменных удовлетворяет всем условиям, это находится в PO.
Если все предложения при преобразовании в дизъюнктивную нормальную форму имеют два термина: один состоит из всех положительных (неотрицаемых) переменных, а другой - из всех отрицательных переменных, то это находится в PO.
Если все предложения представляют собой операцию ИЛИ переменных O(1), она является APX-полной.
Если это экземпляр 2-X(N)OR-SAT, это Min UnCut-complete.
Если это экземпляр X(N)OR-SAT, но не 2-X(N)OR-SAT, это полное кодовое слово.
Если это экземпляр 2-CNF-SAT , это минимальное удаление 2CNF-завершено.
Если все предложения имеют значение Horn или Dual-Horn , то удаление Min Horn завершено.
В противном случае различие между ответом 0 и ненулевым ответом является NP-полным.

Мин.

Следующие условия составляют классификационную теорему для задач Min Ones. ^[1]

Если установка всех переменных false удовлетворяет всем условиям, это находится в PO.
Если каждое предложение может быть записано как CNF подпунктов Horn , оно находится в PO.
Если это экземпляр 2-X(N)OR-SAT, он находится в PO.
Если это экземпляр 2-CNF-SAT , он APX-полный.
Если все предложения представляют собой операцию ИЛИ переменных O(1), она является APX-полной.
Если это экземпляр X(N)OR-SAT, но не 2-X(N)OR-SAT, это полное кодовое слово.
Если каждое предложение может быть записано как CNF подпунктов Dual-Horn , оно является полным с удалением Min Horn.
Если установка всех переменных true удовлетворяет всем условиям, это Poly-APX-полный.
В противном случае найти приемлемое решение будет NP-трудно.

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Ханна, Санджив; Судан, Мадху; Тревизан, Лука; Уильямсон, Дэвид (март 2000 г.). «Аппроксимируемость задач удовлетворения ограничений» (PDF) . СИАМ Дж. Компьютер . 30 (6). СИАМ: 1863–1920 гг. дои : 10.1137/S0097539799349948 .
^ Демейн, Эрик (осень 2014 г.). «Алгоритмические нижние границы: забава с доказательствами твердости, лекция 11, примечания» (PDF) .
^ Jump up to: ^а ^б Агарвал, Амит; Чарикар, Моисей; Макарычев Константин; Макарычев, Юрий (2005). " $O({\sqrt {\log n}})$ Алгоритмы аппроксимации для min UnCut, min 2CNF удаления и задач направленного разреза» . Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений . STOC '05. Нью-Йорк, Нью-Йорк, США: ACM. стр. 573–581.

[kstw-1] Jump up to: ^а ^б ^с ^д ^и Ханна, Санджив; Судан, Мадху; Тревизан, Лука; Уильямсон, Дэвид (март 2000 г.). «Аппроксимируемость задач удовлетворения ограничений» (PDF) . СИАМ Дж. Компьютер . 30 (6). СИАМ: 1863–1920 гг. дои : 10.1137/S0097539799349948 .

[2] Демейн, Эрик (осень 2014 г.). «Алгоритмические нижние границы: забава с доказательствами твердости, лекция 11, примечания» (PDF) .

[acmm-3] Jump up to: ^а ^б Агарвал, Амит; Чарикар, Моисей; Макарычев Константин; Макарычев, Юрий (2005). " $O({\sqrt {\log n}})$ Алгоритмы аппроксимации для min UnCut, min 2CNF удаления и задач направленного разреза» . Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений . STOC '05. Нью-Йорк, Нью-Йорк, США: ACM. стр. 573–581.

[1]

[2]

[3]