El teorema de Valiant-Vazirani es un teorema en la teoría de la complejidad computacional que establece que si existe un algoritmo de tiempo polinomial para Unmbiguous-SAT , entonces NP = RP . Fue probado por Leslie Valiant y Vijay Vazirani en su artículo titulado NP es tan fácil como detectar soluciones únicas publicado en 1986. [1] La prueba se basa en el lema de aislamiento Mulmuley-Vazirani-Vazirani , que posteriormente se utilizó para varios aplicaciones importantes en informática teórica .
El teorema de Valiant-Vazirani implica que el problema de satisfacibilidad booleano , que es NP-completo , sigue siendo un problema computacionalmente difícil incluso si se promete que las instancias de entrada tendrán como máximo una asignación satisfactoria.
Esquema de prueba
Unmbiguous-SAT es el problema de la promesa de decidir si una fórmula booleana dada que tiene como máximo una asignación satisfactoria es insatisfactoria o tiene exactamente una asignación satisfactoria. En el primer caso, un algoritmo para Unmbiguous-SAT debería rechazar, y en el segundo debería aceptar la fórmula. Si la fórmula tiene más de una asignación satisfactoria, entonces no existe ninguna condición sobre el comportamiento del algoritmo. El problema de la promesa Unmbiguous-SAT puede ser decidido por una máquina de Turing no determinista que tenga como máximo una ruta de cómputo aceptable. En este sentido, este problema de promesa pertenece a la clase de complejidad UP (que normalmente solo se define para lenguajes).
La demostración del teorema de Valiant-Vazirani consiste en una reducción probabilística de SAT a SAT tal que, con probabilidad al menos , la fórmula de salida tiene como máximo una asignación satisfactoria y, por lo tanto, satisface la promesa del problema Unmbiguous-SAT. Más precisamente, la reducción es un algoritmo de tiempo polinomial aleatorio que mapea una fórmula booleana con variables a una fórmula booleana tal que
- cada asignación satisfactoria de también satisface , y
- Si es satisfactorio, entonces, con probabilidad al menos , tiene una asignación única y satisfactoria .
Ejecutando la reducción de un número polinomial de veces, cada vez con bits aleatorios independientes nuevos, obtenemos fórmulas . Elegir, obtenemos que la probabilidad de que al menos una fórmula es excepcionalmente satisfactorio es al menos Si es satisfactorio. Esto da una reducción de Turing de SAT a Unmbiguous-SAT ya que se puede invocar un algoritmo supuesto para Unmbiguous-SAT en el. Entonces, la autorreductibilidad aleatoria de SAT se puede utilizar para calcular una asignación satisfactoria, en caso de que exista. En general, esto prueba que NP = RP si Unmbiguous-SAT se puede resolver en RP.
La idea de la reducción es intersecar el espacio solución de la fórmula con hiperplanos afines al azar sobre , dónde se elige uniformemente al azar. Una prueba alternativa se basa en el lema del aislamiento de Mulmuley, Vazirani y Vazirani. Consideran una configuración más general, y aplicada a la configuración aquí, esto da una probabilidad de aislamiento de solo.
Referencias
- ^ Valiente, L .; Vazirani, V. (1986). "NP es tan fácil como detectar soluciones únicas" (PDF) . Informática Teórica . 47 : 85–93. doi : 10.1016 / 0304-3975 (86) 90135-0 .