Por que $ a≤_p \ # set $ se $ a \ no bpp $

Question

Olá e obrigado por me ajudar a entender o seguinte:

Eu realmente não entendo isso, por que se a linguagem $ a \ no BPP $ então $ a≤_p \ $ #Sat $ ?

linguagem A está na classe BPP, se para uma máquina de Turização probabilística m, m saídas 1 para todos $ x \ em um $ em uma probabilidade $ \ GEQ 2/3 $ e para todos $ x \ Not \ em um $ m saídas 1 em uma probabilidade de $ \ leq 1/3 $ e, claro, m deve ser executado em um tempo polinomial em todas as entradas.

Então, se $ a \ no BPP $ , por que isso significa que $ A≤_P \ # SAT $ < / span>? Se m é reduzido a booleano f, significa que vamos obter a saída de 1 em uma probabilidade de $ \ GEQ 2/3 $ para cada $ x \ em $ ? Por quê?

Alguém pode, por favor, mostre-me algoritmicamente ou matemática por que se a linguagem $ a \ no BPP $ então $ a≤_p \ $ #Sat $ ? bastante perdido

Obrigado, apreciaria se você pudesse explicar.

Answer 1

Usando a prova do teorema do Cook-Levin, para cada entrada $ x $ Você pode construir no tempo polinomial uma instância SAT $ \ phi (r, z) $ que codifica" $ m $ aceita quando executado na entrada $ x $ e aleatoriedade $ R $ ". Aqui $ R $ é um vetor de $ m=mathit {poly} (n) $ bits, Representando os pedaços aleatórios de $ m $ , e $ z $ é um vetor auxiliar, com a seguinte propriedade : Em qualquer aceitação de execução de $ m $ , existe exatamente uma configuração de $ Z $ que satisfaz < span class="contêiner matemático"> $ \ phi $ .

Por definição, se $ x \ in l $ então $ \ phi $ tem pelo menos < span class="contentor de matemática"> $ (2/3) 2 ^ m $ Atribuições satisfatórias e se $ x \ notin l $ < Classe Span="Recipiente de Matemática"> $ \ Phi $ tem no máximo $ (1/3) 2 ^ m $ Atribuições satisfatórias. Você pode distinguir entre os dois casos usando uma $ \ mathsf {\ # sáb} $ oracle.