¿Por qué $ A≤_P \ # SAT $ si $ A \ in BPP $

Question

Hola y gracias por ayudarme a entender lo siguiente:

Realmente no entiendo esto, por qué si el lenguaje $ A \ in BPP $ luego $ a≤_p \ #SAT $ ?

Idioma A está en la clase BPP, si para una máquina de Turing Probabilistic M, m, m, m, salidas 1 para todos $ x \ en un $ en una probabilidad $ \ GEQ 2/3 $ , y para todos $ x \ no \ en las salidas de $ m 1 en una probabilidad de $ \ leq 1/3 $ y, por supuesto, M debe ejecutarse en un tiempo polinomial en todas las entradas.

Entonces, si $ a \ in bpp $ , ¿por qué significa que $ A≤_p \ # SAT $ < / span>? Si M se reduce a BOOLEAN F, significa que obtendremos una salida de 1 en una probabilidad de $ \ geq 2/3 $ para cada $ x \ en un $ ? ¿Por qué?

¿Puede alguien mostrarme algoritómico o matemáticamente por qué si el lenguaje $ A \ in bpp $ luego $ a≤_p \ #Sat $ ? bastante perdido

Gracias, apreciaría si pudieras explicarlo.

Answer 1

Uso de la prueba del teorema de Cook-Levin, para cada entrada $ x $ Puede construir en un tiempo polinomial un SAT instancia $ \ PHI (R, Z) $ que codifica" $ m $ acepta cuando se ejecuta en la entrada $ x $ y aleatoriedad $ r $ ". Aquí $ r $ es un vector de $ m=mathit {poly} (n) $ bits, Representando los trozos aleatorios de $ m $ , y $ z $ es un vector auxiliar, con la siguiente propiedad : En cualquier ejecución de aceptación de $ m $ , existe exactamente una configuración de $ z $ que satisface < Span Class="Math-contenedor"> $ \ PHI $ .

Por definición, si $ x \ en l $ luego $ \ phi $ tiene al menos < Span Class="Math-contenedor"> $ (2/3) 2 ^ M $ Asignaciones satisfactorias, y si $ x \ Notin l $ luego Span Class="Math-contenedor"> $ \ PHI $ tiene en la mayoría $ (1/3) 2 ^ M $ Asignaciones satisfactorias. Puede distinguir entre los dos casos utilizando un $ \ mathsf {\ # sat} $ Oracle.