В теории сложности вычислений , ветвь информатики , то Макс / мин СНТ / Ones классификационные теоремы необходимые и достаточные условия, определяющие классы сложности задач об удовлетворении подмножество S булевых отношений. [1] Они похожи на теорему Шефера о дихотомии , которая классифицирует сложность удовлетворения конечных наборов отношений; однако, макс / мин СНТ / Единица классификация теорема дает информацию о сложности аппроксимации оптимального решения задачи , определенной S .
Учитывая множество S дизъюнктов, то проблема удовлетворения ограничений Max (СНТ) , чтобы найти максимальное количество (в весовом случае: максимальная сумма весов) из выполнимых пунктов в S . Точно так же проблема Min CSP состоит в том, чтобы минимизировать количество невыполненных предложений. Задача Max Ones состоит в том, чтобы максимизировать количество логических переменных в S , для которых установлено значение 1 при ограничении, что все предложения удовлетворяются, а проблема Min Ones состоит в том, чтобы минимизировать это число. [2]
При использовании приведенных ниже классификаций класс сложности задачи определяется наивысшей классификацией, которой она удовлетворяет .
Определения
Здесь мы для краткости определим некоторые термины, которые используются в классификациях ниже.
- PO расшифровывается как Polynomial time optimizable; задачи, для которых поиск оптимума может быть выполнен за полиномиальное время, так что приближение к произвольной точности также может быть выполнено за полиномиальное время.
- Конъюнктивная нормальная форма ниже сокращенно обозначается CNF .
- X (N) OR-SAT обозначает проблему выполнимости, которая представляет собой AND нескольких логических линейных уравнений, которые могут быть записаны как предложения XOR. Ровно один литерал в каждом предложении XOR должен быть инвертирован (например,). См. XOR-SAT .
- Min UnCut-complete относится к классу сложности, исторически определенному в терминах проблемы с именем Min UnCut. Такие проблемы сложны для APX, но сфакторное приближение. [3]
- Min 2CNF-Deletion-complete - еще один класс сложности, исторически определяемый через проблему. Такие проблемы сложны для APX, но сприближение. [3]
- Ближайшее полное кодовое слово - еще один такой класс сложности. Такие проблемы невозможно приблизить с точностью до фактор для некоторых .
- Min Horn-Deletion-complete - еще один такой класс сложности. Такие проблемы невозможно приблизить с точностью до фактор для некоторых , но находятся в Poly-APX, поэтому имеют некоторое приближение полиномиального множителя.
Классификационные теоремы
Макс. CSP
Следующие условия составляют классификационную теорему для задач Max CSP. [1]
- Если установка всех переменных в истину или все переменные в ложь удовлетворяет всем пунктам, это находится в PO.
- Если все предложения при преобразовании в дизъюнктивную нормальную форму имеют два члена, один из которых состоит из всех положительных (не связанных) переменных, а другой - из отрицательных переменных, то он находится в PO.
- В противном случае проблема APX-полная .
Макс.
Следующие условия составляют классификационную теорему для задач Max One. [1]
- Если установка всех переменных в истину удовлетворяет всем пунктам, она находится в ЗП.
- Если каждое предложение может быть записано как 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-complete .
- Если это экземпляр 2-CNF-SAT , он является Poly-APX-complete.
- Если установка всех или всех переменных, кроме одной, в false, удовлетворяет каждому предложению, это означает, что Poly-APX-complete.
- Это NP-трудно отличить ответ от 0 и ненулевой ответ , если установка всех переменных ложных удовлетворяет всем пункты.
- В противном случае найти даже возможное решение NP-сложно.
Мин. CSP
Следующие условия составляют классификационную теорему для задач Min CSP. [1]
- Если установка всех переменных в ложь или все переменные в истину удовлетворяет всем пунктам, это находится в PO.
- Если все предложения при преобразовании в дизъюнктивную нормальную форму имеют два члена, один из которых состоит из всех положительных (не связанных) переменных, а другой - из отрицательных переменных, то он находится в PO.
- Если все предложения являются OR для O (1) переменных, это APX-полное.
- Если это экземпляр 2-X (N) OR-SAT, он является Min UnCut-complete.
- Если это экземпляр X (N) OR-SAT, но не 2-X (N) OR-SAT, он является полным ближайшим кодовым словом.
- Если это экземпляр 2-CNF-SAT , это Min 2CNF-Deletion-complete.
- Если все пункты являются Horn или Dual-Horn , это завершено для удаления Min Horn.
- В противном случае различие между ответом 0 и ненулевым ответом является NP-полным.
Мин.
Следующие условия составляют классификационную теорему для задач Минона. [1]
- Если установка всех переменных в ложь удовлетворяет всем пунктам, она находится в ЗП.
- Если каждое предложение может быть записано как CNF подпунктов Horn , оно находится в PO.
- Если это экземпляр 2-X (N) OR-SAT, он находится в PO.
- Если это экземпляр 2-CNF-SAT , он является APX-полным.
- Если все предложения являются OR для O (1) переменных, это APX-полное.
- Если это экземпляр X (N) OR-SAT, но не 2-X (N) OR-SAT, он является полным ближайшим кодовым словом.
- Если каждое предложение может быть записано как CNF из подпунктов Dual-Horn , оно является завершенным для удаления Min Horn.
- Если установка всех переменных в истину удовлетворяет всем пунктам, то это Poly-APX-complete.
- В противном случае трудно даже найти подходящее решение.
Смотрите также
Рекомендации
- ^ a b c d e Кханна, Санджив; Судан, Мадху; Тревизан, Лука; Уильямсон, Дэвид (март 2000 г.). «Аппроксимируемость задач удовлетворения ограничений» (PDF) . SIAM J. Comput . СИАМ. 30 (6): 1863–1920. DOI : 10,1137 / S0097539799349948 .
- ^ Демейн, Эрик (осень 2014 г.). «Алгоритмические нижние границы: развлечения с доказательствами твердости, лекция 11, примечания» (PDF) .
- ^ а б Агарвал, Амит; Чарикар, Моисей; Макарычев, Константин; Макарычев, Юрий (2005). "алгоритмы аппроксимации для задач min UnCut, min 2CNF и направленных разрезов " . Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений . STOC '05. Нью-Йорк, Нью-Йорк, США: ACM. стр. 573–581.