Алгоритм Карлоффа – Цвика

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

Алгоритм основан на полуопределенном программировании . Его можно дерандомизировать, используя, например, методы из ^{[ 2 ]} чтобы получить детерминированный алгоритм с полиномиальным временем и теми же гарантиями аппроксимации.

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

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

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

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

Ссылки

^ Перейти обратно: ^а ^б Карлофф, Х.; Цвик, У. (1997), «Алгоритм приближения 7/8 для MAX 3SAT?», Труды 38-го ежегодного симпозиума по основам информатики , стр. 406–415, CiteSeerX 10.1.1.51.1351 , doi : 10.1109/SFCS .1997.646129 , ISBN 978-0-8186-8197-4 , S2CID 15447333 .
^ Сивакумар, Д. (19 мая 2002 г.), «Алгоритмическая дерандомизация с помощью теории сложности», Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений , стр. 619–626, doi : 10.1145/509907.509996 , ISBN 1581134959 , S2CID 94045
^ Хастад, Дж. (2001), «Некоторые оптимальные результаты неаппроксимируемости», Journal of the ACM , 48 (4): 798–859, CiteSeerX 10.1.1.638.2808 , doi : 10.1145/502090.502098 , S2CID 5120748 .

[Karloff-1] Перейти обратно: ^а ^б Карлофф, Х.; Цвик, У. (1997), «Алгоритм приближения 7/8 для MAX 3SAT?», Труды 38-го ежегодного симпозиума по основам информатики , стр. 406–415, CiteSeerX 10.1.1.51.1351 , doi : 10.1109/SFCS .1997.646129 , ISBN 978-0-8186-8197-4 , S2CID 15447333 .

[2] Сивакумар, Д. (19 мая 2002 г.), «Алгоритмическая дерандомизация с помощью теории сложности», Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений , стр. 619–626, doi : 10.1145/509907.509996 , ISBN 1581134959 , S2CID 94045

[3] Хастад, Дж. (2001), «Некоторые оптимальные результаты неаппроксимируемости», Journal of the ACM , 48 (4): 798–859, CiteSeerX 10.1.1.638.2808 , doi : 10.1145/502090.502098 , S2CID 5120748 .

[ 1 ]

[ 2 ]

[ 3 ]