МАКСЭКСАТ

MAXEkSAT — это задача теории сложности вычислений , которая представляет собой максимизирующую версию булевой проблемы выполнимости 3SAT . В MAXEkSAT каждое предложение имеет ровно k литералов, каждый с разными переменными, и находится в конъюнктивной нормальной форме . Они называются формулами k-CNF. Проблема состоит в том, чтобы определить максимальное количество предложений, которое может быть удовлетворено присвоением истинности переменным в предложениях.

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

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

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

Существует простой рандомизированный полиномиальный алгоритм, который обеспечивает $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ -приближение к MAXEkSAT: независимо установить для каждой переменной значение true с вероятностью ⁠ 1/2 , ⁠ в противном случае установите значение false.

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

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

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

Более надежный анализ (например, в ^[1]) показывает, что мы фактически удовлетворим по крайней мере $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ -доля предложений постоянная доля времени (зависящая только от k ), без потери $\textstyle \epsilon$ .

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

Хотя приведенный выше алгоритм эффективен, не очевидно, как устранить его зависимость от случайности. Проверка всех возможных случайных назначений эквивалентна наивному подходу грубой силы, поэтому может занять экспоненциальное время. Один умный способ дерандомизировать вышеизложенное за полиномиальное время основан на работе над кодами, исправляющими ошибки , удовлетворяющими $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ доля предложений за полиномиальное время от входного размера (хотя показатель степени зависит от k ).

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

Определение

$S\subseteq \{0,1\}^{n}$ является $ℓ$ -независимым источником, если для равномерно выбранного случайного значения $(x 1, x 2, ..., x n) \in S,$ $x 1, x 2, ..., x n$ являются $ℓ$ -независимыми случайными величинами .

Факт 1

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

Факт 2

Напомним, что BCH _{2, m , d} – это $[n=2^{m},n-1-\lceil {d-2}/2\rceil m,d]_{2}$ линейный код.

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

Краткое описание алгоритма

Алгоритм работает путем генерации $BCH 2,log n, ℓ +1$ , вычисления его двойника (который как набор является $ℓ$ -независимым источником) и обработки каждого элемента (кодового слова) этого источника как присвоения истинности n переменным в φ . Хотя бы один из них будет удовлетворять хотя бы $1 - 2 - ℓ$ предложений φ , если φ находится в форме kCNF, $k = ℓ$ .

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

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

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

См. также

Ссылки

^ «Макс-САТ» (PDF) . Архивировано из оригинала (PDF) 23 сентября 2015 г. Проверено 1 сентября 2014 г.
^ Хосеп Аргелич и Фелип Манья. Точные решатели Max-SAT для задач со сверхограничениями . В журнале эвристики 12 (4) стр. 375-392. Спрингер, 2006.
^ Жолен, Л.; Уолтер, Э. (2002). «Гарантированная робастная нелинейная минимаксная оценка» (PDF) . Транзакции IEEE при автоматическом управлении . 47 (11): 1857–1864. дои : 10.1109/TAC.2002.804479 .

Внешние ссылки

Заметки по теории кодирования в Массачусетском технологическом институте

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

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

[3] Жолен, Л.; Уолтер, Э. (2002). «Гарантированная робастная нелинейная минимаксная оценка» (PDF) . Транзакции IEEE при автоматическом управлении . 47 (11): 1857–1864. дои : 10.1109/TAC.2002.804479 .

[1]

[2]

[3]