Perché $ a≤_p \ # sat $ Se $ a \ in BPP $

Question

Ciao e grazie per avermi aiutato a capire quanto segue:

Io davvero non capisco questo, perché se la lingua $ a \ in BPP $ quindi $ A≤_P \ #Sat $ ?

Lingua A è in classe BPP, se per una macchina di tentazione probabilistica M, M output 1 per tutte le $ x \ in $ in una probabilità $ \ Geq 2/3 $ e per tutti $ x \ non \ in un $ M outputs 1 in una probabilità di $ \ Leq 1/3 $ e ovviamente M deve funzionare in un momento polinomiale su tutti gli ingressi.

Quindi se $ a \ in BPP $ , perché significa che $ a≤_p \ # sat $ < / span>? Se M è ridotto a Boolean F, significa che ottenere la produzione di 1 in una probabilità di $ \ Geq 2/3 $ per ogni $ x \ in $ ? Perché?

Qualcuno può mostrarmi algoritmicamente o matematicamente perché se la lingua $ a \ in BPP $ quindi $ a≤_P #Sat $ ? abbastanza perso

Grazie, apprezzerebbe se potessi spiegare lungo.

Answer 1

Utilizzo della prova del teorema del cook-levin, per ogni ingresso $ x $ È possibile costruire in tempo polinomiale A istanza SAT $ \ phi (r, z) $ che codifica" $ m $ accetta quando viene eseguito su input $ x $ e casualità $ r $ ". Qui $ R $ è un vettore di $ m=mathit {poly} (n) $ bit, Rappresentando i bit casuali di $ m $ e $ z $ è un vettore ausiliario, con la seguente proprietà : In qualsiasi esecuzione dell'accettazione della $ M $ , c'è esattamente un'impostazione di $ z $ che soddisfi < Span Class="Math-Container"> $ \ PHI $ .

Per definizione, se $ x \ in l $ quindi $ \ phi $ ha almeno < Span Class="Math-Container"> $ (2/3) 2 ^ m $ Assegnazioni soddisfacenti e se $ x \ Notin L $ Allora < Span Class="Math-Container"> $ \ PHI $ ha al massimo $ (1/3) 2 ^ m $ Assegnazioni soddisfacenti. È possibile distinguere tra i due casi utilizzando una classe $ \ mathsf {\ # sat} $ Oracle.