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 SAT no ambiguo , entonces NP = RP . Leslie Valiant y Vijay Vazirani lo demostraron en su artículo titulado NP is as easy as detecting unique solutions 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 insatisfacible 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 hay ninguna condición sobre el comportamiento del algoritmo. El problema de promesa Unambiguous-SAT puede ser resuelto por una máquina de Turing no determinista que tenga como máximo una ruta de cálculo que la acepte, 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, da como resultado una secuencia de fórmulas G 0 ,..., G n tales 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 necesaria para el argumento NP = RP , pero 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 no ambiguo que tiene éxito con una probabilidad de al menos Ω(1/ n ). Es decir, si F es insatisfacible, la fórmula de salida siempre es insatisfacible, y si F es satisfacible, entonces la fórmula de salida tiene una asignación satisfactoria única con probabilidad Ω(1/ n ).
Ahora, suponiendo que SAT no ambiguo se puede 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 insatisfacible, entonces A rechaza todos los G i porque son insatisfacibles, 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 RP promiseUP .
Una prueba alternativa se basa en el lema de aislamiento de Mulmuley, Vazirani y Vazirani. Consideran un contexto más general y, aplicado al contexto aquí, esto da una probabilidad de aislamiento de solo .
