Алгоритмы суперполиномиального приближения по времени для MAX 3SAT

20

Теорема PCP гласит, что для MAX 3SAT не существует алгоритма полиномиального времени, чтобы найти назначение, удовлетворяющее условиям 7/8 выполнимой формулы 3SAT, если только .P = N Р7/8+εпзнак равноNп

Существует тривиальный алгоритм полиномиального времени, который удовлетворяет из пунктов. Итак, можем ли мы добиться большего успеха, чем если мы допустим суперполиномиальные алгоритмы? Какие отношения аппроксимации мы можем достичь с помощью алгоритмов квазиполиномиального времени ( ) или с помощью алгоритмов субэкспоненциального времени ( )? Я ищу ссылки на любые такие алгоритмы.7 / 8 + ε п O ( журнал N ) 2 О ( п )7/87/8+εNО(журналN)2о(N)

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

Ответы:

29

Можно получить приближение 7/8 для MAX3SAT, которое выполняется за времени без особых проблем. Вот идея. Разделите набор переменных на групп по переменных в каждой. Для каждой группы попробуйте все способов назначения переменных в группе. Для каждой приведенной формулы запустите аппроксимацию Karloff и Zwick . Выведите назначение, удовлетворяющее максимальному количеству предложений, из всех этих испытаний.2 O ( ε п ) O ( 1 / ε ) ε п 2 ε п 7 / 87/8+ε/82О(εN)О(1/ε)εN2εN7/8

Дело в том, что существует некоторый переменный блок, такой, что оптимальное назначение (ограниченное этим блоком) уже удовлетворяет -размещению максимального числа удовлетворенных предложений. Вы получите правильные эти дополнительные пункты, и вы получите от оставшейся части оптимального, используя Карлоффа и Цвика.7 / 8ε7/8

Это интересный вопрос, можно ли получить времени для одного и того же типа аппроксимации. Существует «Линейная гипотеза PCP», что 3SAT может быть уменьшен за полиномиальное время до MAX3SAT, так что:2О(ε2N)

  • если экземпляр 3SAT выполним, то экземпляр MAX3SAT полностью выполним,
  • если экземпляр 3SAT является неудовлетворительным, то экземпляр MAX3SAT не удовлетворяется 7/8 , и7/8+ε
  • уменьшение увеличивает размер формулы только на множитель .поLY(1/ε)

Предполагая эту линейную гипотезу PCP, приближение -время 7/8 для всех и повлечет за собой то, что 3SAT находится за времени, для всех . (Здесь - количество предложений.) В доказательстве используется лемма о разрежении Импальяццо, Патури и Зейна. 7 / 8 + ε с ε 2 ε п ε м2О(εсм)7/8+εсε2εNεм

Райан Уильямс
источник
Спасибо Раяно за хороший ответ, можем ли мы принять это в качестве доказательства против существования алгоритмов квазиполиных или суб-экспонент времени с коэффициентами аппроксимации лучше , чем ? 7/8
Мухаммед Аль-Туркистани
18

Чтобы немного переформулировать то, что Райан Уильямс написал в своем последнем абзаце:

Т(N)знак равно2N1-о(1)(7/8+1/(журналжурналN)0,000001)Т(N)2о(N)7/8

Райан О'Доннелл
источник