$ a \ in bpp $の場合$ a≦_p \＃sat $

Question

こんにちは、私が次のことを理解してくれてありがとう：

私はこれを本当に理解していません、言語 $ a \ in bpp $ で $a≤_p\ #sat $ ？

言語Aは、確率的なチューリングマシンMの場合、m、m、m、m個のすべての $ x \ $ x \ $ x \ $ x \ \ x \ \ x \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x "Math-Container"> $ \ geq 2/3 $ 、およびすべての $ x \ not \ nでは、$ m出力1の確率で1出力 $ \ leq 1/3 $ およびもちろんmはすべての入力で多項式時に実行されなければなりません。

だからbpp $ の $ a \の場合、 $a≤_p\＃sat $ < /スパン>？ Mがブール値Fに縮小されている場合、 $ \ geq 2/3 $ の確率で1の出力を取得することを意味します。数学コンテナ "> $ X \ $ ？なぜ？

誰かが言語 $ a \ in bpp $ で$ a \ a \ and a \ and a≦_p \を言語 $ a \を見せてくれることができますか#sat $ ？かなり失われた

ありがとう、あなたが仲良くすることができたら感謝します。

Answer 1

Cook-Levin定理の証明を使用して、すべての入力 $ x $ の場合は、SATインスタンス $ \φ（r、z）$ $ m $ は、入力を実行するときに受け入れます。 $ x $ とrandomness $ r $ "。ここでspan class="math-container"> $ R $ は、 $ m=mathit {poly}（n）$ ビットのベクトルです。 $ m $ のランダムビットを表す、 $ z $ は補助ベクトルです。 ： $ m $ の受付実行では、 $ z $ の設定が1つあります。 SPAN CLASS="math-container"> $ \φ$ 。

定義によって、 $ x \ in l $ の場合、 $ \φ$ は少なくとも< SPAN CLASS="math-container"> $（2/3）2 ^ m $ $ x \ notin l $ の場合SPAN CLASS="Math-Container"> $ \ PHI $ は、 $（1/3）2 ^ m $ を満足しています。 $ \ mathsf {\＃sat} $ Oracleを使用して2つのケースを区別することができます。