Эквивалентная формулировка теоремы PCP является: Для Макса 3-SAT это -трудного различать выполнимые формулы и формулы , где не более группу фракций из пунктов являются выполнимы (для некоторого ).r r < 1
Существует ли какая-либо известная теорема о дихотомии, которая классифицирует все максимальные значения CSP на основании наличия у них жестких пробелов или нет?
Редактировать 16 декабря 2010 : MAX CSP с жестким зазором означает, что проблема имеет оптимальный коэффициент неприемлемости. Например, 3SAT имеет жесткий разрыв в месте один , так как это полиномиальное время аппроксимируемо к фактору , но это -трудного получить множитель приближения даже тогда , когда все пункты являются выполнимы.Н Р 7 / 8 + ε
источник
Теорема 5.14 Ханны, Судана, Тревизана и Уильямсона [KSTW01] дает теорему о дихотомии для версий с промежутками с совершенной полнотой для булевых задач MaxCSP.
[KSTW01] Санджив Ханна, Мадху Судан, Лука Тревизан и Дэвид П. Уильямсон. Аппроксимируемость постоянных проблем удовлетворения. SIAM Journal of Computing , 30 (6): 1863–1920, 2001. http://dx.doi.org/10.1137/S0097539799349948
источник
Если я не ошибаюсь, окончательный результат на этом фронте принадлежит Наде Кринью, которая показала, что каждая проблема в MAX CSP либо разрешима по времени, либо MAX SNP-сложна .
источник