Warum ist $ a ≤_p \ # Sat $, wenn $ a \ in BPP $
Frage
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
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.
Lösung
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
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