МАКС-3САТ - MAX-3SAT

MAX-3SAT - это проблема вычислительной сложности в информатике . Он обобщает проблему логической выполнимости (SAT), которая является проблемой решения, рассматриваемой в теории сложности . Это определяется как:

Дана 3-CNF- формула Φ (т. Е. С не более чем 3 переменными на одно предложение), найдите присваивание, которое удовлетворяет наибольшему количеству предложений.

MAX-3SAT - это каноническая полная задача для класса сложности MAXSNP (полная показана на Papadimitriou pg. 314).

Аппроксимируемость

Версия решения MAX-3SAT является NP-полной . Следовательно, решение за полиномиальное время может быть достигнуто только в том случае, если P = NP . Однако с помощью этого простого алгоритма можно добиться приближения с точностью до коэффициента 2:

• Выведите решение, в котором выполняется большинство предложений, когда либо все переменные = ИСТИНА, либо все переменные = ЛОЖЬ.
• Каждому предложению удовлетворяет одно из двух решений, поэтому одно решение удовлетворяет как минимум половине предложений.

В алгоритме Карлофф-Цвик работает в полиномиальное время и удовлетворяет ≥ 7/8 из пунктов.

Теорема 1 (непроксимируемость)

Теорема PCP означает, что существует ε > 0 такое, что (1- ε ) -аппроксимация MAX-3SAT является NP-трудной .

Доказательство:

Любая NP-полная задача по теореме PCP . Для X ∈ L , A 3-КНФ формула Ψ _х сконструирован таким образом, что ${\ Displaystyle L \ в {\ mathsf {PCP}} (О (\ log (п)), О (1))}$

• x ∈ L ⇒ Ψ _x выполнимо
• x ∉ L ⇒ выполнимо не более (1 - ε ) m клозов _x .

Verifier V считывает все требуемые биты сразу, т.е. выполняет неадаптивные запросы. Это действительно так, потому что количество запросов остается постоянным.

• Пусть q будет количеством запросов.
• Перечисляя все случайные строки R _i ∈ V , мы получаем строки poly ( x ), начиная с длины каждой строки .${\ Displaystyle г (х) = О (\ журнал | х |)}$
• Для каждого R _i
  • V выбирает q позиций i ₁ , ..., i _q и булеву функцию f _R : {0,1} ^q -> {0,1} и принимает тогда и только тогда, когда f _R (π (i ₁ , ... , i _q )). Здесь π относится к доказательству, полученному от Oracle.

Затем мы пытаемся найти булеву формулу, чтобы смоделировать это. Введем булевы переменные x ₁ , ..., x _l , где l - длина доказательства. Чтобы продемонстрировать, что Verifier работает за вероятностное полиномиальное время , нам нужно соответствие между количеством выполнимых предложений и вероятностью, которую принимает Verifier.

• Для каждого R добавьте предложения, представляющие f _R ( x _i1 , ..., x _iq ), используя 2 ^q предложений SAT . Пункты длины q преобразуются в длину 3 путем добавления новых (вспомогательных) переменных, например x ₂ ∨ x ₁₀ ∨ x ₁₁ ∨ x ₁₂ = ( x ₂ ∨ x ₁₀ ∨ y _R ) ∧ ( y _R ∨ x ₁₁ ∨ x ₁₂ ) . Для этого требуется не более q 2 ^q 3-SAT пунктов.
• Если z ∈ L, то
  • существует доказательство π такое, что V ^π ( z ) принимает для любого R _i .
  • Все пункты удовлетворяются, если x _i = π ( i ) и вспомогательные переменные добавлены правильно.
• Если ввод z ∉ L, то
  • Для каждого присвоения x ₁ , ..., x _l и y _R соответствующее доказательство π ( i ) = x _i заставляет Проверяющий отклонять половину всех R ∈ {0,1} ^{r (| z | )} .
    • Для каждого R одно предложение, представляющее f _R, не выполняется.
    • Следовательно, часть пунктов не работает.${\ displaystyle {\ frac {1} {2}} {\ frac {1} {q2 ^ {q}}}}$

Можно сделать вывод, что если это верно для каждой NP-полной задачи, то теорема PCP должна быть верной.

Теорема 2.

Хастад демонстрирует более точный результат, чем теорема 1, т. Е. Наиболее известное значение ε .

Он создает PCP Verifier для 3-SAT, который считывает только 3 бита из Proof.

Для каждого ε > 0 существует PCP-верификатор M для 3-SAT, который считывает случайную строку r длины и вычисляет позиции запроса i _r , j _r , k _r в доказательстве π и бит b _r . Он принимает тогда и только тогда, когда 'π ( i _r ) ⊕ π ( j _r ) ⊕ π ( k _r ) = b _r .${\ Displaystyle О (\ журнал (п))}$

Проверяющий имеет полноту (1− ε ) и надежность 1/2 + ε (см. PCP (сложность) ). Проверяющий удовлетворяет

${\ Displaystyle Z \ в L \ подразумевает \ существует \ pi Pr [V ^ {\ pi} (x) = 1] \ geq 1- \ epsilon}$

${\ displaystyle z \ not \ in L \ подразумевает \ forall \ pi Pr [V ^ {\ pi} (x) = 1] \ leq {\ frac {1} {2}} + \ epsilon}$

Если бы первое из этих двух уравнений было приравнено к «= 1», как обычно, можно было бы найти доказательство π, решив систему линейных уравнений (см. MAX-3LIN-EQN ), подразумевающую P = NP .

• Если z ∈ L , выполняется доля ≥ (1 - ε ) клозов.
• Если z ∉ L , то для части R (1/2 - ε ) противоречат клозам 1/4.

Этого достаточно, чтобы доказать жесткость отношения аппроксимации

${\ displaystyle {\ frac {1 - {\ frac {1} {4}} ({\ frac {1} {2}} - \ epsilon)} {1- \ epsilon}} = {\ frac {7} { 8}} + \ epsilon '}$

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

MAX-3SAT (B) - это ограниченный частный случай MAX-3SAT, где каждая переменная встречается не более чем в предложениях B. До того, как теорема PCP была доказана, Пападимитриу и Яннакакис показали, что для некоторой фиксированной константы B эта задача является MAX SNP-сложной. Следовательно, с теоремой PCP это также сложно для APX. Это полезно, потому что MAX-3SAT (B) часто можно использовать для получения снижения с сохранением PTAS, чего нельзя сделать с помощью MAX-3SAT . Доказательства явных значений B включают: все B ≥ 13 и все B ≥ 3 (что является наилучшим возможным).

Более того, хотя проблема решения 2SAT решается за полиномиальное время, MAX-2SAT (3) также является APX-трудным.

Наилучший возможный коэффициент приближения для MAX-3SAT (B) как функция от B не меньше и не больше , если NP = RP . Некоторые явные ограничения на приближаемости констант при определенных значениях B известны. Берман, Карпински и Скотт доказали, что для «критических» экземпляров MAX-3SAT, в которых каждый литерал встречается ровно дважды и каждое предложение имеет размер 3, проблема является сложной аппроксимацией для некоторого постоянного множителя. ${\ Displaystyle 7/8 + \ Omega (1 / B)}$${\ displaystyle 7/8 + O (1 / {\ sqrt {B}})}$

MAX-EkSAT - это параметризованная версия MAX-3SAT, в которой каждое предложение имеет ровно k литералов для k ≥ 3. Его можно эффективно аппроксимировать коэффициентом аппроксимации, используя идеи теории кодирования . ${\ Displaystyle 1- (1/2) ^ {к}}$

Доказано, что случайные экземпляры MAX-3SAT могут быть аппроксимированы с точностью до множителя8/9.

Рекомендации

Конспект лекций Калифорнийского университета в Беркли Заметки по теории кодирования в Университете Буффало