Algoritmo de Karloff-Zwick

El algoritmo de Karloff-Zwick , en la teoría de la complejidad computacional , es un algoritmo de aproximación aleatoria que toma como entrada una instancia del problema de satisfacibilidad booleana MAX-3SAT . Si la instancia es satisfacible, el peso esperado de la asignación encontrada es al menos 7/8 del óptimo. Existe una fuerte evidencia (aunque no una demostración matemática ) de que el algoritmo alcanza 7/8 del óptimo incluso en instancias MAX-3SAT insatisfacibles. Howard Karloff y Uri Zwick presentaron el algoritmo en 1997. ^{[ 1 ]}

El algoritmo se basa en programación semidefinida . Se puede eliminar la aleatoriedad utilizando, por ejemplo, las técnicas de ^{[ 2 ]} para obtener un algoritmo determinista de tiempo polinomial con las mismas garantías de aproximación.

Para el problema MAX-E3SAT relacionado, en el que se garantiza que todas las cláusulas de la fórmula 3SAT de entrada tengan exactamente tres literales, el algoritmo de aproximación aleatoria simple , que asigna un valor de verdad a cada variable de forma independiente y uniforme al azar, satisface 7/8 de todas las cláusulas en promedio, independientemente de si la fórmula original es satisfacible. Además, este algoritmo simple también se puede desaleatorizar fácilmente utilizando el método de expectativas condicionales . Sin embargo, el algoritmo de Karloff-Zwick no requiere la restricción de que la fórmula de entrada deba tener tres literales en cada cláusula. ^{[ 1 ]}

Partiendo de trabajos previos sobre el teorema PCP , Johan Håstad demostró que, suponiendo que P ≠ NP, ningún algoritmo de tiempo polinomial para MAX 3SAT puede alcanzar una relación de rendimiento superior a 7/8, incluso cuando se restringe a instancias satisfacibles del problema en las que cada cláusula contiene exactamente tres literales. Por lo tanto, tanto el algoritmo de Karloff-Zwick como el algoritmo simple anterior son óptimos en este sentido. ^{[ 3 ]}