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

МАКС-3САТ проблема в вычислительная сложность подполе Информатика. Это обобщает Проблема логической выполнимости (SAT), который является проблема решения рассматривается в теория сложности. Это определяется как:

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

МАКС-3САТ канонический полный задача для класса сложности MAXSNP (полностью показано в Papadimitriou стр. 314).

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

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

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

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

Теорема 1 (неприближаемость)

В Теорема PCP означает, что существует ε > 0 такое, что (1-ε) -приближение МАКС-3САТ является NP-жесткий.

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

Любой НП-полный проблема ${\displaystyle L\in {\mathsf {PCP}}(O(\log(n)),O(1))}$ посредством Теорема PCP. Для x ∈ L, а 3-CNF формула Ψ_Икс построен так, что

• Икс ∈ L ⇒ Ψ_Икс выполнимо
• Икс ∉ L ⇒ не более (1-ε)м статьи Ψ_Икс удовлетворительны.

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

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

Далее мы пытаемся найти Булево формула для моделирования этого. Введем булевы переменные Икс₁,...,Икс_л, куда л - длина доказательства. Чтобы продемонстрировать, что Verifier работает в Вероятностный полиномиальное время, нам нужно соответствие между количеством выполнимых предложений и вероятностью, которую принимает Проверяющий.

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

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

Теорема 2.

Håstad ^[1] демонстрирует более точный результат, чем теорема 1, т. е. наиболее известное значение ε.

Он конструирует верификатор PCP для 3-СБ который читает только 3 бита из Доказательства.

Для каждого ε > 0 существует PCP-верификатор M для 3-СБ который читает случайную строку r длины ${\displaystyle O(\log(n))}$ и вычисляет позиции запроса я_р, j_р, k_р в доказательстве π и немного б_р. Он принимает тогда и только тогда, когда

π(я_р) ⊕ π(j_р) ⊕ π(k_р) = б_р.

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

${\displaystyle z\in L\implies \exists \pi Pr[V^{\pi }(x)=1]\geq 1-\epsilon }$

${\displaystyle z\not \in L\implies \forall \pi Pr[V^{\pi }(x)=1]\leq {\frac {1}{2}}+\epsilon }$

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

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

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

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

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

МАКС-3САТ (В) ограниченный частный случай МАКС-3САТ где каждая переменная встречается не более чем в B статьи. Перед Теорема PCP было доказано, Пападимитриу и Яннакакис^[2] показал, что для некоторой фиксированной постоянной B, эта проблема сложна MAX SNP. Следовательно, с теоремой PCP, это также сложно для APX. Это полезно, потому что МАКС-3САТ (В) часто можно использовать для получения снижения с сохранением PTAS таким образом, чтобы МАКС-3САТ не можешь. Доказательства явных значений B включают: все В ≥ 13,^[3][4] и все В ≥ 3^[5] (что лучше всего).

Более того, хотя проблема решения 2СБ разрешима за полиномиальное время, МАКС-2САТ (3) также APX-жесткий.^[5]

Наилучшее возможное отношение аппроксимации для МАКС-3САТ (В), как функция B, по крайней мере ${\displaystyle 7/8+\Omega (1/B)}$ и самое большее ${\displaystyle 7/8+O(1/{\sqrt {B}})}$,^[6] пока не НП=RP. Некоторые явные оценки констант аппроксимируемости для некоторых значений B известны.^[7][8][9] Берман, Карпински и Скотт доказали, что для «критических» случаев МАКС-3САТ в котором каждый литерал встречается ровно дважды и каждое предложение имеет размер 3, проблема заключается в сложности аппроксимации для некоторого постоянного множителя.^[10]

МАКС-ЭКСАТ является параметризованной версией МАКС-3САТ где в каждом пункте есть точно ${\displaystyle k}$ литералы, для k ≥ 3. Его можно эффективно аппроксимировать с помощью отношения аппроксимации ${\displaystyle 1-(1/2)^{k}}$ используя идеи из теория кодирования.

Доказано, что случайные экземпляры МАКС-3САТ можно аппроксимировать с точностью до множителя ${\displaystyle 8/9}$.^[11]

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

1. Хостад, Йохан (2001). «Некоторые оптимальные результаты несовместимости». Журнал ACM. 48 (4): 798–859. CiteSeerX  10.1.1.638.2808. Дои:10.1145/502090.502098.
2. Христос Пападимитриу и Михалис Яннакакис, Оптимизация, аппроксимация и классы сложности, Труды двадцатого ежегодного симпозиума ACM по теории вычислений, стр.229-234, 2–04 мая 1988 г.
3. Рудич и др., "Теория вычислительной сложности", IAS / Park City Mathematics Series, 2004, стр. 108 ISBN  0-8218-2872-X
4. Санджив Арора "Вероятностная проверка доказательств и трудность задач аппроксимации., "Пересмотренная версия диссертации, представленная в отделении CS, Калифорнийский университет в Беркли, в августе 1994 года. CS-TR-476-94. Раздел 7.2.
5. Аузиелло, Г., Крещенци, П., Гамбози, Г., Канн, В., Маркетти Спаккамела, А., и Протаси, М. (1999), Сложность и приближение. Комбинаторные задачи оптимизации и их свойства аппроксимируемости, Springer-Verlag, Берлин. Раздел 8.4.
6. Лука Тревизан. 2001. Результаты о неприближаемости для задач оптимизации на примерах ограниченной степени. В материалах тридцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '01). ACM, Нью-Йорк, Нью-Йорк, США, 453-461. DOI = 10.1145 / 380752.380839 http://doi.acm.org/10.1145/380752.380839
7. О некоторых более точных результатах о неприближаемости, Петр Берман и Марек Карпински, Proc. ICALP 1999, страницы 200-209.
8. П. Берман, М. Карпински, Нижние границы улучшенной аппроксимации для оптимизации малых вхождений. ECCC TR 03-008 (2003)
9. П. Берман, М. Карпинский и А. Д. Скотт, Трудность аппроксимации и выполнимость экземпляров SAT с ограниченным вхождением,ECCC TR 03-022 (2003).
10. П. Берман, М. Карпинский и А. Д. Скотт, Аппроксимационная твердость коротких симметричных экземпляров MAX-3SAT,ECCC TR 03-049 (2003).
11. В. Ф. де ла Вега и М. Карпински, 9/8-аппроксимационный алгоритм для случайного MAX-3SAT,ECCC TR 02-070 (2002); RAIRO-Operations Research 41 (2007), стр.95-107]

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