Teorema de Valiant-Vazirani

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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.[1] 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[editar | editar código-fonte]

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 , 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 com variáveis para uma fórmula Booleana de tal forma que

  • Toda atribuição satisfeitora de também satisfaz
  • Se  é satisfatível, então, com probabilidade de pelo menos , tem uma única atribuição satisfeitora .

Executando a redução polinomial um número de vezes, cada vez com novos bits independentes e randômicos, obtemos as fórmulas . Escolhendo , temos que a probabilidade de que pelo menos uma fórmula é univocamente satisfatível e, no mínimo, se é 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 . 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 com  hiperplanos afins aleatórios sobre , onde é 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 .

Referências

  1. Valiant, L.; Vazirani, V. (1986). «NP is as easy as detecting unique solutions» (PDF). Theoretical Computer Science. 47: 85–93. doi:10.1016/0304-3975(86)90135-0