МАКСЭКСАТ - MAXEkSAT

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

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

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

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

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

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

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

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

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

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

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

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

Определение

${\ Displaystyle S \ substeq \ {0,1 \} ^ {п}}$является ℓ -wise независимого источника , если для равномерно выбраны случайным образом ( х ₁ , х ₂ , ..., х _п ) ∈ S , х ₁ , х ₂ , ..., х _п являются ℓ -wise независимых случайных величин .

Факт 1

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

Факт 2

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

Там существует ℓ -wise независимого источника размера , а именно двойной из МПБ _{2, бревенчатый н , л +1} код, который представляет собой линейный код. Поскольку каждый код BCH может быть представлен как вычисляемое за полиномиальное время ограничение связанного кода Рида-Соломона , которое само по себе является строго явным, существует алгоритм полиномиального времени для нахождения такого присвоения x _i . Доказательство факта 2 можно найти на Dual of BCH, независимом источнике . ${\ Displaystyle О (п ^ {\ lfloor \ ell / 2 \ rfloor})}$

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

Алгоритм работа по генерации ВСНО _{2, бревенчатый н , ℓ + 1} , вычисление двойственного (который в качестве множества является ℓ -wise независимого источника) и обрабатывать каждый элемент (кодовые слова) из этого источника в качестве присвоения истинности к п переменных в φ . По крайней мере один из них будет удовлетворять , по крайней мере 1 - 2 ^{- л} из положений ф , всякий раз , когда φ в kCNF форме, к = л .

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

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

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

Смотрите также

использованная литература

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

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