МАКС-3САТ

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

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

MAX-3SAT — это каноническая полная задача для класса сложности MAXSNP (полная показана в Пападимитриу, стр. 314).

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

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

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

Алгоритм Карлоффа-Цвика работает за полиномиальное время и удовлетворяет ≥ 7/8 условий. Хотя этот алгоритм является рандомизированным, его можно дерандомизировать, используя, например, методы из ^[1] чтобы получить детерминированный (полиномиальный) алгоритм с теми же гарантиями аппроксимации.

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

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

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

Любая NP-полная задача ⁠ $L\in {\mathsf {PCP}}(O(\log(n)),O(1))$ ⁠ по теореме PCP . Для x ∈ L формула 3-КНФ Ψ _x строится так, что

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

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

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

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

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

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

Теорема 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Было доказано, что случайные экземпляры MAX-3SAT можно аппроксимировать с точностью до коэффициента. ⁠ 8 / 9 ⁠ . ^[12]

Ссылки

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

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

[1] Сивакумар, Д. (19 мая 2002 г.), «Алгоритмическая дерандомизация с помощью теории сложности», Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений , стр. 619–626, doi : 10.1145/509907.509996 , ISBN 1581134959 , S2CID 94045

[2] Хостад, Йохан (2001). «Некоторые оптимальные результаты о неаппроксимируемости». Журнал АКМ . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . дои : 10.1145/502090.502098 . S2CID 5120748 .

[3] Христос Пападимитриу и Михалис Яннакакис, Классы оптимизации, аппроксимации и сложности, Труды двадцатого ежегодного симпозиума ACM по теории вычислений, стр. 229–234, 2–04 мая 1988 г.

[4] Рудич и др., «Теория сложности вычислений», Серия IAS / Park City Mathematics, 2004 г., стр. 108 ISBN 0-8218-2872-X

[5] Санджив Арора, « Вероятностная проверка доказательств и сложность задач аппроксимации », исправленная версия диссертации, представленной в отделе CS Калифорнийского университета в Беркли в августе 1994 года. CS-TR-476-94. Раздел 7.2.

[acgkmsp-6] Jump up to: Перейти обратно: ^а ^б Осиелло Г., Крещенци П., Гамбози Г., Канн В., Маркетти Спаккамела А. и Протаси М. (1999), Сложность и аппроксимация. Комбинаторные задачи оптимизации и их свойства аппроксимации, Шпрингер-Верлаг, Берлин. Раздел 8.4.

[7] Лука Тревизан. 2001. Результаты о неаппроксимируемости задач оптимизации на экземплярах ограниченной степени. В материалах тридцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '01). ACM, Нью-Йорк, Нью-Йорк, США, 453–461. DOI=10.1145/380752.380839 http://doi.acm.org/10.1145/380752.380839

[8] О некоторых более жестких результатах о неаппроксимируемости, Петр Берман и Марек Карпински, Proc. ICALP 1999, страницы 200–209.

[9] П. Берман и М. Карпински, Нижние границы улучшенного приближения при оптимизации малых вхождений, ЕССС ТР 03-008 (2003 г.)

[10] П. Берман, М. Карпински и А.Д. Скотт, Твердость аппроксимации и выполнимость ограниченных экземпляров SAT, ЕССС ТР 03-022 (2003) .

[11] П. Берман, М. Карпински и А.Д. Скотт, Твердость аппроксимации коротких симметричных экземпляров MAX-3SAT, ЕССС ТР 03-049 (2003).

[12] В. Ф. де ла Вега и М. Карпински, Алгоритм аппроксимации 9/8 для случайного MAX-3SAT, ЕССС ТР 02-070 (2002) ; RAIRO-Operations Research 41 (2007), стр. 95–107]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]