Почему $ a≤_p \ # Sat $, если $ a \ in bpp $

Question

Привет и спасибо, что помог мне понять следующее:

Я действительно не понимаю этого, почему, если язык $ a \ in bpp $ Тогда $ a≤_p \ #Sat $ ?

Язык A находится в классе BPP, если для вероятностной машины Turing M, M, M, выходов 1 для всех $ x \ in $ в вероятности $ \ Geq 2/3 $ , и для всех $ x \ not \ in a $ m Выход 1 в вероятности $ \ leq 1/3 $ и, конечно, m должен работать в многочленом времени на всех входах.

Так, если $ a \ in bpp $ , почему это означает, что $ a≤_p \ # SAT $ < / span>? Если M уменьшается до логического значения F, это означает, что мы получим вывод 1 в вероятности $ \ geq 2/3 $ для каждого $ x \ in $ ? Почему?

Может кто-нибудь, пожалуйста, покажу мне алгоритмически или математически, почему, если язык $ a \ in bpp $ Тогда $ a≤_p \ #Sat $ ? довольно потерян

Спасибо, будет признателен, если бы вы могли объяснить вместе.

Answer 1

Использование доказательства теоремы Cook-Levin, для каждого ввода $ x $ Вы можете построить в многочленом времени A SAT Axcare $ m $ При запуске на входе $ x $ и случайность $ R $ ". Здесь $ R $ - вектор $ m=\ mathit {poly} (n) $ bits, Представление случайных битов $ m $ , и $ z $ - это вспомогательный вектор, со следующим свойством : В любом приемном пробеге $ m $ есть ровно одна настройка $ Z $ Что удовлетворяет < SPAN CLASS= «Математический контейнер»> $ \ phi $ .

по определению, если $ x \ in l $ Тогда $ \ phi $ имеет по крайней мере < Spaness Class="Математический контейнер"> $ (2/3) 2 ^ m $ Удовлетворенные заданиями, и если $ x \ Notin l $ тогда < Spaness Class= «Математический контейнер»> $ \ phi $ имеет максимально возможный $ (1/3) 2 ^ m $ Удовлетворенные заданиями. Вы можете различить двумя случаями, используя $ \ mathsf {\ # SAT} $ Oracle.