Derandomizing Valiant-Vazirani?

29

O teorema de Valiant-Vazirani diz que, se houver um algoritmo de tempo polinomial (determinístico ou aleatório) para distinguir entre uma fórmula SAT que possui exatamente uma tarefa satisfatória e uma fórmula insatisfatória - então NP = RP . Este teorema é provado mostrando que UNIQUE-SAT é NP- hard sob reduções aleatórias .

Sujeito a conjecturas plausíveis de derandomização, o Teorema pode ser fortalecido para "uma solução eficiente para UNIQUE-SAT implica NP = P ".

Meu primeiro instinto foi pensar que, implícita, existe uma redução determinística de 3SAT para UNIQUE-SAT, mas não está claro para mim como essa redução em particular pode ser des randomizada.

Minha pergunta é: o que se acredita ou se sabe sobre "reduções derandomizing"? É / deve ser possível? E no caso de VV?

Como o UNIQUE-SAT está completo para o PromiseNP sob reduções aleatórias, podemos usar uma ferramenta de des aleatorização para mostrar que "uma solução de tempo polinomial determinística para o UNIQUE-SAT implica que PromiseNP = PromiseP ?

Henry Yuen
fonte
4
Quanto ao último parágrafo, PromiseP = PromiseNP é equivalente a P = NP.
Tsuyoshi Ito 29/07

Respostas:

31

Sob as premissas corretas de des aleatorização (consulte Klivans-van Melkebeek ), você obtém o seguinte: Existe um tempo polimático computável st para todos ,f(ϕ)=(ψ1,,ψk)f(ϕ)=(ψ1,,ψk)ϕϕ

  • Se for satisfatório, pelo menos um dos possui exatamente uma tarefa satisfatória.ϕϕψiψi
  • Se não é satisfatório, todos os são insatisfatórios.ϕϕψiψi

Você precisa de polinômio k no comprimento de . Provavelmente não pode ser feito para .ϕϕk=1k=1

Lance Fortnow
fonte
@LanceFortnow implica que o lema de isolamento Vazirani-Valiant possa ser derandomizado e, portanto, implica redução determinística no que daria ? P=BPPP=BPPP=BPPP=BPPSATSATP=NPP=NP
T ....
11
Não. Você precisa de uma suposição mais forte do que P = BPP para derandomizar Valiant-Vazirani (mais uma vez refiro-lhe Klivans-van Melkebeek). Mesmo se você derandomizar Valiant-Vaizarni, isso apenas fornecerá o resultado mencionado acima - você não obteria P = NP a menos que tivesse um algoritmo que pudesse resolver a satisfação com testemunhas únicas.
precisa
@LanceFortnow Só para ficar claro. Podemos obter apenas por ou é essencial que (com o estado de conhecimento que temos) é provável que tenhamos que derandomizar o VV para obter para (essa é uma consulta um pouco diferente do que perguntar se P = BPP fornece redução determinística SAT, pois pode não ser essencial que o VV seja necessário no início local para obter NP em BPP ^ {oplus P}). PP=BPPPPP=BPPPP=BPPP=BPPPP=BPPPPP=BPPP
T ....
22

Apenas para referência, eu me deparei com este artigo realmente interessante hoje, que evidencia que uma redução determinística é improvável:

Dell, H., Kabanets, V., Watanabe, O., & van Melkebeek, D. (2012). O lema do isolamento Valiant-Vazirani é melhorável? ECCC TR11-151

Eles argumentam que isso não é possível, a menos que NP esteja contido em P / poli.

Henry Yuen
fonte