El teorema de Valiant-Vazirani es un teorema de la teoría de la complejidad computacional que establece que si existe un algoritmo de tiempo polinomial para Unambiguous-SAT , entonces NP = RP . Leslie Valiant y Vijay Vazirani lo demostraron en su artículo titulado NP es tan fácil como detectar soluciones únicas publicado en 1986. [1]
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.
Unambiguous-SAT es el problema de 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 Unambiguous-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 promesa Unambiguous-SAT puede ser decidido por una máquina de Turing no determinista que tiene como máximo una ruta de cálculo de aceptación, por lo que pertenece a la versión de promesa de la clase de complejidad UP (la clase UP como tal solo está definida para lenguajes).
La prueba del teorema de Valiant-Vazirani consiste en una reducción probabilística que dada una fórmula F en n variables, genera una secuencia de fórmulas G 0 ,..., G n tal que:
La idea de la reducción es intersecar sucesivamente el espacio solución de la fórmula F con n hiperplanos lineales aleatorios en .
Como consecuencia (no es necesario para el argumento NP = RP , pero sí de interés independiente), si elegimos uno de los G i al azar, obtenemos una reducción aleatoria con error unilateral de SAT a SAT inequívoco que tiene éxito con probabilidad al menos Ω(1/ n ). Es decir, si F es insatisfactorio, la fórmula de salida siempre es insatisfactoria, y si F es satisfacible, entonces la fórmula de salida tiene una asignación satisfactoria única con probabilidad Ω(1/ n ).
Ahora, suponiendo que Unambiguous-SAT se pueda resolver mediante un algoritmo de tiempo polinomial A , obtenemos un algoritmo RP para SAT ejecutando A en G i para cada i ≤ n . Si F es insatisfactorio, entonces A rechaza todos los G i porque son insatisfactibles, mientras que si F es satisfacible, entonces A acepta algunos G i con una probabilidad de al menos 1/4. (Podemos mejorar la probabilidad de aceptación repitiendo la reducción varias veces).
De manera más general, este argumento muestra incondicionalmente que NP está incluido en RPpromesaUP .
Una prueba alternativa se basa en el lema de aislamiento de Mulmuley, Vazirani y Vazirani. Consideran un entorno más general y, aplicado al entorno aquí, esto da una probabilidad de aislamiento de sólo .
