Алгоритм Карлоффа–Цвика в теории вычислительной сложности — это рандомизированный алгоритм приближения, принимающий в качестве входных данных экземпляр задачи булевой выполнимости 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]