МАКСЭКСАТ - MAXEkSAT

МАКСЭКСАТ проблема в теория сложности вычислений это версия максимизации задачи булевой выполнимости 3СБ. В MAXEkSAT каждое предложение имеет ровно k литералы, каждый с различными переменными, и находится в конъюнктивная нормальная форма. Они называются формулами k-CNF. Проблема состоит в том, чтобы определить максимальное количество предложений, которое может быть выполнено путем присвоения истинности переменным в предложениях.

Мы говорим, что алгоритм А обеспечивает α-приближение в MAXEkSAT, если для некоторого фиксированного положительного α меньше или равно 1, и каждая формула kCNF φ, А может найти присвоение истинности переменным φ что удовлетворит по крайней мере α-доля максимального количества выполнимых пунктов φ.

Поскольку NP-жесткий k-SAT проблема (для k ≥ 3) эквивалентно определению того, имеет ли соответствующий экземпляр MAXEkSAT значение, равное количеству предложений, MAXEkSAT также должен быть NP-трудным, что означает, что не существует алгоритма полиномиального времени, если только P = NP. Естественно, что следующий вопрос - найти приблизительные решения: какое наибольшее действительное число? α <1 так что некоторые явные P (сложность) алгоритм всегда находит решение размера α · OPT, куда OPT это (потенциально трудно найти) максимальное назначение.

Алгоритм аппроксимации

Существует простой рандомизированный алгоритм с полиномиальным временем, который обеспечивает ${displaystyle extstyle (1- {гидроразрыв {1} {2 ^ {k}}})}$ -приближение к MAXEkSAT: независимо установить для каждой переменной значение true с вероятностью¹⁄₂, в противном случае установите значение false.

Любая статья c неудовлетворен, только если все его k составные литералы оцениваются как ложные. Поскольку каждый литерал в предложении имеет¹⁄₂ шанс получить истинное значение независимо от любого значения истинности любого из других литералов, вероятность того, что все они ложны, равна ${displaystyle extstyle ({гидроразрыв {1} {2}}) ^ {k} = {гидроразрыв {1} {2 ^ {k}}}}$ . Таким образом, вероятность того, что c действительно доволен ${displaystyle extstyle 1- {гидроразрыв {1} {2 ^ {k}}}}$ , поэтому индикаторная переменная ${displaystyle extstyle 1_ {c}}$ (то есть 1, если c верно и 0 в противном случае) имеет ожидание ${displaystyle extstyle 1- {гидроразрыв {1} {2 ^ {k}}}}$ . Сумма всех индикаторных переменных по всем ${displaystyle extstyle | C |}$ статьи ${displaystyle (extstyle 1- {frac {1} {2 ^ {k}}}) | C |}$ , так что линейность ожидания мы удовлетворяем ${displaystyle extstyle (1- {гидроразрыв {1} {2 ^ {k}}})}$ доля предложений в ожидании. Потому что оптимальное решение не может удовлетворить больше всего ${displaystyle extstyle | C |}$ пунктов, у нас есть, что ${displaystyle extstyle ALG = (1- {frac {1} {2 ^ {k}}}) cdot | C |> (1- {frac {1} {2 ^ {k}}}) cdot OPT}$ , поэтому алгоритм находит ${displaystyle extstyle geq (1- {гидроразрыв {1} {2 ^ {k}}})}$ приближение к истинному оптимальному решению в ожидании.

Несмотря на свои высокие ожидания, этот алгоритм может иногда наткнуться на решения, стоимость которых ниже, чем ожидание, которое мы вычислили выше. Однако по большому количеству испытаний средняя доля удовлетворенных пунктов будет стремиться к ${displaystyle extstyle (1- {гидроразрыв {1} {2 ^ {k}}})}$ . Это подразумевает две вещи:

Должно существовать задание, удовлетворяющее как минимум ${displaystyle extstyle (1- {гидроразрыв {1} {2 ^ {k}}})}$ фракция статей. Если бы не было, мы никогда не смогли бы достичь такого большого значения в среднем за большое количество испытаний.
Если мы запустим алгоритм большое количество раз, по крайней мере половина испытаний (в ожидании) удовлетворит некоторые ${displaystyle extstyle (1- {гидроразрыв {2} {2 ^ {k}}})}$ доля статей. Это связано с тем, что любая меньшая дробь снизит среднее значение настолько, что алгоритм должен иногда удовлетворять более 100% предложений, чтобы вернуться к своему ожиданию ${displaystyle extstyle (1- {гидроразрыв {2} {2 ^ {k}}})}$ , чего не может быть. Расширение этого с помощью Неравенство Маркова, по крайней мере, некоторые ${displaystyle extstyle ({frac {1} {1 + 2 ^ {k} epsilon}})}$ -доля испытаний (в ожидании) удовлетворит по крайней мере ${displaystyle extstyle (1- {frac {1} {2 ^ {k}}} - эпсилон)}$ -доля статей. Поэтому при любом положительном ${displaystyle extstyle epsilon}$ , требуется лишь полиномиальное количество случайных испытаний, пока мы не ожидаем найти задание, удовлетворяющее по крайней мере ${displaystyle extstyle (1- {гидроразрыв {1} {2 ^ {k}}} - эпсилон)}$ фракция статей.

Более надежный анализ (например, в ^[1]) показывает, что на самом деле мы будем удовлетворять по крайней мере ${displaystyle extstyle (1- {гидроразрыв {1} {2 ^ {k}}})}$ -доля предложений постоянная часть времени (зависит только от k), без потери ${displaystyle extstyle epsilon}$ .

Дерандомизация

Хотя приведенный выше алгоритм эффективен, не очевидно, как избавиться от его зависимости от случайности. Испытание всех возможных случайных назначений эквивалентно наивному подходу грубой силы, поэтому может потребоваться экспоненциальное время. Один умный способ дерандомизировать указанное выше за полиномиальное время зависит от работы в коды исправления ошибок, удовлетворяя ${displaystyle extstyle (1- {гидроразрыв {1} {2 ^ {k}}})}$ доля предложений во времени, полиномиальная в размере ввода (хотя показатель степени зависит от k).

Чтобы найти алгоритм, нам нужно одно определение и два факта.

Определение

${displaystyle Ssubseteq {0,1} ^ {n}}$ является ℓнезависимый источник, если для равномерно выбранного случайного (Икс₁, Икс₂, ..., Икс_п) ∈ S, Икс₁, Икс₂, ..., Икс_п находятся ℓразумно независимый случайные переменные.

Факт 1

Обратите внимание, что такое назначение можно найти среди элементов любого ℓнезависимый источник над п бинарные переменные. Это легче увидеть, если вы поймете, что ℓ-в смысле независимый источник - это просто любой набор двоичных векторов над {0, 1}^п с тем свойством, что все ограничения этих векторов на ℓ координаты должны представлять 2^ℓ возможных двоичных комбинаций равное количество раз.

Факт 2

Напомним, что BCH_2,м,d является ${displaystyle [n = 2 ^ {m}, n-1-lceil {d-2} / 2ceil m, d] _ {2}}$ линейный код.

Существует ℓразумно независимый источник размера ${displaystyle O (n ^ {lfloor ell / 2floor})}$ , а именно двойник BCH_{2, журналп,ℓ+1} code, который является линейным кодом. Поскольку каждый Код BCH можно представить как вычислимое за полиномиальное время ограничение связанного Рид Соломон код, который сам по себе является строго явным, существует алгоритм с полиномиальным временем для нахождения такого присвоения Икс_яс. Доказательство факта 2 можно найти на Dual of BCH - независимый источник.

Схема алгоритма

Алгоритм работает путем генерации BCH_{2, журналп,ℓ+1}, вычисляя его дуал (который как набор является ℓнезависимый источник) и обработка каждого элемента (кодового слова) этого источника как присвоение истинности п переменные в φ. Хотя бы один из них удовлетворяет как минимум 1-2^−ℓ пунктов φ, в любое время φ находится в форме kCNF, k = ℓ.

Связанные проблемы

Есть много проблем, связанных с выполнимостью булевых формул конъюнктивной нормальной формы.

Проблемы с решением:
- 2СБ
- 3СБ
Задачи оптимизации, цель которых - максимизировать количество удовлетворяемых пунктов:
- МАКС-СБ, и соответствующая взвешенная версия Взвешенный MAX-SAT
- МАКСИМУМ-kSAT, где в каждом пункте ровно k переменные:
  - МАКС-2САТ
  - МАКС-3САТ
  - МАКСЭКСАТ
- Задача частичной максимальной выполнимости (PMAX-SAT) требует максимального количества пунктов, которое может быть удовлетворено любым назначением данного подмножества пунктов. Остальные пункты должны быть выполнены.
- Задача мягкой выполнимости (soft-SAT), заданная для набора задач SAT, требует максимального количества наборов, которое может быть выполнено при любом назначении.^[2]
- Проблема минимальной выполнимости.
Задачу MAX-SAT можно распространить на случай, когда переменные проблема удовлетворения ограничений принадлежат множеству реалов. Проблема сводится к поиску наименьшего q так что q-расслабленное пересечение из ограничений не пусто.^[3]

внешняя ссылка

[1] «Макс-САТ» (PDF). Архивировано из оригинал (PDF) на 2015-09-23. Получено 2014-09-01.

[2] Хосеп Аргелих и Фелип Манья. Точные решатели Max-SAT для задач с чрезмерными ограничениями. В Journal of Heuristics 12 (4) pp. 375-392. Спрингер, 2006.

[3] Jaulin, L .; Уолтер, Э. (2002). «Гарантированная робастная нелинейная минимаксная оценка» (PDF). IEEE Transactions по автоматическому контролю. 47.

[1]

[2]

[3]