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

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

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

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

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

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

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

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

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

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

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

Любой НП-полный проблема посредством Теорема PCP. Для x ∈ L, а 3-CNF формула ΨИкс построен так, что

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

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

  • Позволять q быть количеством запросов.
  • Перечисление всех случайных строк ря ∈ V, получаем poly (Икс) строк, поскольку длина каждой строки .
  • Для каждого ря
    • V выбирает q позиции я1,...,яq и логическая функция жр: {0,1}q-> {0,1} и принимает тогда и только тогда, когда жр(π (i1,...,яq)). Здесь π относится к доказательству, полученному от Oracle.

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

  • Для каждого рдобавьте пункты, представляющие жр(Иксi1,...,Иксiq) используя 2q СИДЕЛ статьи. Пункты длины q преобразуются в длину 3 путем добавления новых (вспомогательных) переменных, например. Икс2 ∨ Икс10 ∨ Икс11 ∨ Икс12 = ( Икс2 ∨ Икс10 ∨ yр) ∧ ( yр ∨ Икс11 ∨ Икс12). Для этого требуется максимум q2q 3-СБ статьи.
  • Если z ∈ L тогда
    • существует доказательство π такое, что Vπ (z) принимает за каждый ря.
    • Все пункты удовлетворяются, если Икся = π(я) и вспомогательные переменные добавлены правильно.
  • Если ввод z ∉ L тогда
    • Для каждого задания Икс1,...,Иксл и yрs, соответствующее доказательство π (я) = Икся заставляет Проверяющий отклонить половину всех р ∈ {0,1}р(|z|).
      • Для каждого р, один пункт, представляющий жр терпит неудачу.
      • Поэтому часть статей не удается.

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

Теорема 2.

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

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

Для каждого ε > 0 существует PCP-верификатор M для 3-СБ который читает случайную строку r длины и вычисляет позиции запроса яр, jр, kр в доказательстве π и немного бр. Он принимает тогда и только тогда, когда

π(яр) ⊕ π(jр) ⊕ π(kр) = бр.

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

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

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

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

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

МАКС-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, по крайней мере и самое большее ,[6] пока не НП=RP. Некоторые явные оценки констант аппроксимируемости для некоторых значений B известны.[7][8][9] Берман, Карпински и Скотт доказали, что для «критических» случаев МАКС-3САТ в котором каждый литерал встречается ровно дважды и каждое предложение имеет размер 3, проблема заключается в сложности аппроксимации для некоторого постоянного множителя.[10]

МАКС-ЭКСАТ является параметризованной версией МАКС-3САТ где в каждом пункте есть точно литералы, для k ≥ 3. Его можно эффективно аппроксимировать с помощью отношения аппроксимации используя идеи из теория кодирования.

Доказано, что случайные экземпляры МАКС-3САТ можно аппроксимировать с точностью до множителя .[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]

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