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 $\mathrm{\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^{\prime }(x_1,\dots ,x_n)$ de tal forma que

• Toda atribuição satisfeitora de $F^{\prime }$ também satisfaz $F$
• Se $F$ é satisfatível, então, com probabilidade de pelo menos $\mathrm{\Omega }(1/n)$, $F^{\prime }$ 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{\text{'}}_1,\dots ,F{\text{'}}_t$. Escolhendo $t=O(n)$, temos que a probabilidade de que pelo menos uma fórmula $F{\text{'}}_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{\text{'}}_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 ideia 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 $\mathrm{\Omega }(1/n^8)$.