Warum ist $ a ≤_p \ # Sat $, wenn $ a \ in BPP $

Question

Hallo und danke, dass Sie mir helfen, Folgendes zu verstehen:

Ich verstehe das wirklich nicht, warum wenn Sprache $ a \ in BPP $ dann $ a ≤_p \ #Sat $ ?

Sprache A befindet sich in der BPP-Klasse, wenn für eine probabilistische Turing-Maschine M, M-Ausgänge 1 für alle $ x \ in einem $ in einer Wahrscheinlichkeit $ \ GEQ 2/3 $ , und für alle $ x \ NICHT \ in einem $ m Ausgängen 1 in einer Wahrscheinlichkeit von $ \ LEQ 1/3 $ und natürlich muss m in einer Polynomzeit an allen Eingängen ausgeführt werden.

wenn also $ a \ in BPP $ , warum bedeutet es, dass $ a ≤_p \ # SAT $ < / span>? Wenn m auf boolean f reduziert wird, bedeutet dies, dass wir in einer Wahrscheinlichkeit von $ \ geq 2/3 $ für jede $ x \ in einem $ ? Warum?

Kann mir jemand algorithmisch oder mathematisch zeigen, warum, wenn Sprache $ A \ in BPP $ dann $ a ≤_p \ #Sat $ ? ganz verloren

Vielen Dank, würde sich freuen, wenn Sie miteinander erklären könnten.

Answer 1

Verwenden des Nachweiss des Koch-Levin-Satzes, für jeden Eingang $ x $ Sie können in der Polynomzeit eine SAT-Instanz $ \ phi (R, Z) $ wodurch" $ M $ akzeptiert, wenn der Eingang ausgeführt wird $ x $ und zufällig $ R $ ". Hier $ R $ ist ein Vektor von $ m=mathit {poly} (n) $ Bits, Vertretung der zufälligen Bits von $ M $ und $ Z $ ist ein Hilfsvektor mit der folgenden Eigenschaft : In jedem Annahme des Laufs von $ M $ gibt es genau eine Einstellung von $ Z $ was erfüllt < Span-Klasse="Math-Container"> $ \ phi $ .

per Definition, wenn $ x \ in L $ dann $ \ phi $ mindestens < Span-Klasse="Math-Container"> $ (2/3) 2 ^ M $ Zufriedenheitszuweisungen, und wenn $ X \ NOTIN L $ dann < Span-Klasse="Math-Container"> $ \ phi $ hat höchstens $ (1/3) 2 ^ M $ Befriedigende Aufträge. Sie können zwischen den beiden Fällen mit einem $ \ mathsf {\ # SAT} $ Oracle unterscheiden.