Teorema de Valiant-Vazirani

O Teorema de Valiant–Vazirani  é um teorema na teoria da complexidade computacional. Foi provado por Leslie Valiant e Vijay Vazirani em um artigo intitulado "NP is as easy as detecting unique solutions", publicado em 1986. O teorema afirma que, se existe um algoritmo de tempo polinomial para SAT-não-ambíguo, então NP=RP. A prova é baseada no lema do isolamento de Mulmuley–Vazirani–Vazirani , que, posteriormente, foi utilizado por uma grande quantidade de aplicações na teoria da ciência da computação.

O teorema de Valiant–Vazirani implica que o Problema da satisfatibilidade booleana, que é NP-completo, continua a ser um problema computacionalmente difícil mesmo se as instâncias de entrada são forçadas a ter no máximo uma atribuição satisfeitora.

Esboço da prova

SAT-não-ambíguo é o problema de promessa de decidir se uma dada fórmula Booleana que tem no máximo uma atribuição satisfeitora é insatisfatível ou se tem exatamente uma atribuição satisfeitora. No primeiro caso, um algoritmo para SAT-não-ambíguo deve rejeitar, e, no segundo, ele deve aceitar a fórmula. Se a fórmula tiver mais do que uma atribuição satisfeitora, não há condição sobre o comportamento do algoritmo. O problema de promessa SAT-não-ambíguo pode ser decidido por uma máquina de Turing não-determinística que tem, no máximo, um ramo de aceitação. Neste sentido, esse problema de promessa pertence à classe de complexidade UP (que geralmente só é definido para linguagens).

A prova do teorema de Valiant–Vazirani consiste em uma redução probabilística de SAT para SAT tal que, com probabilidade de pelo menos $\Omega (1/n)$, a fórmula de saída tem, no máximo, uma atribuição sateitora, e, portanto, satisfaz a promessa do problema SAT-não-ambíguo. Mais precisamente, a redução é um algoritmo randômico de tempo polinomial que mapeia uma fórmula Booleana $F(x_{1},\dots ,x_{n})$ com $n$ variáveis $x_{1},\dots ,x_{n}$ para uma fórmula Booleana $F'(x_{1},\dots ,x_{n})$ de tal forma que

• Toda atribuição satisfeitora de $F'$ também satisfaz $F$
• Se $F$ é satisfatível, então, com probabilidade de pelo menos $\Omega (1/n)$, $F'$ tem uma única atribuição satisfeitora $(a_{1},\dots ,a_{n})$.

Executando a redução polinomial um número $t$ de vezes, cada vez com novos bits independentes e randômicos, obtemos as fórmulas $F'_{1},\dots ,F'_{t}$. Escolhendo $t=O(n)$, temos que a probabilidade de que pelo menos uma fórmula $F'_{i}$ é univocamente satisfatível e, no mínimo, $1/2$ se $F$ é satisfatível. Isso dá uma redução Turing de SAT para SAT-não-ambíguo já que um suposto algoritmo para SAT-não-ambíguo pode ser invocado em $F'_{i}$. Em seguida, a auto-redutibilidade randômica de SAT pode ser usada para calcular uma atribuição satisfeitora, que deveria existir. No geral, isso prova que NP=RP-se SAT-não-ambíguo pode ser resolvido em RP.

A idéia de que a redução é para interseccionar o espaço de solução da fórmula $F$ com $k$ hiperplanos afins aleatórios sobre ${\text{GF}}(2)^{n}$, onde $k\in \{1,\dots ,n\}$ é escolhido uniformemente ao acaso. Uma prova alternativa é baseada no lema do isolamento de Mulmuley, Vazirani, e Vazirani. Eles consideraram uma definição mais geral e aplicada para a configuração, o que dá uma probabilidade de isolamento de apenas $\Omega (1/n^{8})$.