Алгоритм Карлоффа-Цвика - Karloff–Zwick algorithm

В Алгоритм Карлоффа-Цвика, в теория сложности вычислений, это рандомизированный алгоритм аппроксимации взяв пример МАКС-3САТ Проблема логической выполнимости как вход. Если экземпляр является выполнимым, то ожидаемый вес найденного назначения составляет не менее 7/8 оптимального. Есть веские доказательства (но не математическое доказательство ), что алгоритм достигает 7/8 от оптимального даже на неудовлетворительных экземплярах MAX-3SAT. Говард Карлофф и Ури Цвик представил алгоритм в 1997 году.^[1]

Сравнение со случайным назначением

Для связанной задачи MAX-E3SAT, в которой все предложения входной формулы 3SAT гарантированно имеют ровно три литерала, простой рандомизированный алгоритм аппроксимации который присваивает значение истинности каждой переменной независимо и равномерно наугад, удовлетворяет 7/8 всех предложений в ожидании, независимо от того, выполнима ли исходная формула. Кроме того, этот простой алгоритм также может быть легко дерандомизированный с использованием метод условных ожиданий. Однако алгоритм Карлоффа – Цвика не требует ограничения, согласно которому входная формула должна иметь три литерала в каждом предложении.^[1]

Оптимальность

Основываясь на предыдущей работе над Теорема PCP, Йохан Хастад показали, что, предполагая P ≠ NP, никакой алгоритм с полиномиальным временем для MAX 3SAT не может достичь коэффициента производительности, превышающего 7/8, даже если он ограничен выполнимыми экземплярами проблемы, в которых каждое предложение содержит ровно три литерала. Следовательно, как алгоритм Карлоффа – Цвика, так и описанный выше простой алгоритм являются оптимальными в этом смысле.^[2]

Рекомендации