Жесткие пробелы в проблемах максимального удовлетворения ограничений?

12

Эквивалентная формулировка теоремы PCP является: Для Макса 3-SAT это -трудного различать выполнимые формулы и формулы , где не более группу фракций из пунктов являются выполнимы (для некоторого ).r r < 1NPrr<1

Существует ли какая-либо известная теорема о дихотомии, которая классифицирует все максимальные значения CSP на основании наличия у них жестких пробелов или нет?

Редактировать 16 декабря 2010 : MAX CSP с жестким зазором означает, что проблема имеет оптимальный коэффициент неприемлемости. Например, 3SAT имеет жесткий разрыв в месте один , так как это полиномиальное время аппроксимируемо к фактору , но это -трудного получить множитель приближения даже тогда , когда все пункты являются выполнимы.Н Р 7 / 8 + ε7/8NP7/8+ϵ

Мухаммед Аль-Туркистани
источник

Ответы:

18

Прасад Рагхавендра в лучшей статье STOC'08 подтвердил гипотезу дихотомии для приближения Max-CSP к предположению об уникальных играх. Это не то, как он представил это первоначально, но он действительно выступал с презентациями, представляющими вещи таким образом пару лет спустя, например, в IAS, где это было записано на видео: http://www.math.ias.edu/seminars/abstract ? событие = 36669

Отличие от показаний твердости по SNP состоит в том, что здесь мы говорим о количественно оптимальных результатах.

Дана Мошковиц
источник
3
что означает «количественно оптимальный»?
Суреш Венкат
3
Коэффициент твердости, который соответствует наиболее известному алгоритму аппроксимации
Дана Мошковиц
6

Теорема 5.14 Ханны, Судана, Тревизана и Уильямсона [KSTW01] дает теорему о дихотомии для версий с промежутками с совершенной полнотой для булевых задач MaxCSP.

[KSTW01] Санджив Ханна, Мадху Судан, Лука Тревизан и Дэвид П. Уильямсон. Аппроксимируемость постоянных проблем удовлетворения. SIAM Journal of Computing , 30 (6): 1863–1920, 2001. http://dx.doi.org/10.1137/S0097539799349948

Цуёси Ито
источник
Интересная статья. Как эта теорема о дихотомии связана с результатом Рагхавендры в ответе Даны?
Мухаммед Аль-Туркистани
Я думаю, что результаты довольно разные. Теорема в [KSTW01], о которой я упоминал в этом ответе, касается версии совершенной полноты, тогда как результат Рагхавендры - нет. Теорема в [KSTW01] о булевой CSP, тогда как Рагавендра о CSP в любой области. Но вы должны проверить сами, потому что я плохо знаю статью Рагхавендры.
Цуёси Ито
4

Если я не ошибаюсь, окончательный результат на этом фронте принадлежит Наде Кринью, которая показала, что каждая проблема в MAX CSP либо разрешима по времени, либо MAX SNP-сложна .

Суреш Венкат
источник
MAX 2-SAT является MAX SNP-трудным, но очень легко разрешимым для удовлетворительных случаев (2-SAT то время как 3-SAT, как известно, не находится в ). Это -трудного иметь -аппроксимации для Макса 3-СБ даже для выполнимых случаев (для любого ). Р Н Р 7 / 8 + & epsi ; & epsi ; > 0PPNP7/8+ϵϵ>0
Мухаммед Аль-Туркистани