为什么$a≤_p\＃sat $如果在bpp $中的$ a \

Question

你好，谢谢你帮助我了解以下内容：

我真的不明白这一点，为什么如果语言 $ a \ in bpp $ 然后 $a≤_p\ #sat $ ？

语言a在bpp类中，如果对于概率图形机m，m，m输出1对于所有 $ x \中的$ 中的概率 $ \ geq 2/3 $ ，以及所有 $ x \ not \以$ m输出1的概率 $ \ leq 1/3 $ ，当然m必须在所有输入上的多项式时间内运行。

所以如果 $ a \ in bpp $ ，为什么 $a≤_p\＃sat $ < / span>？如果m减少到布尔的f，则意味着我们将在 $ \ geq 2/3 $ 的概率中以1的概率来获取1的输出。数学集装箱“> $ x \以$ ？为什么？

有人可以请某人或数学方式向我展示为什么语言 $ a \ in bpp $ 然后 $a≤_p\ #sat $ ？相当丢失

谢谢，如果你能解释一下，将欣赏。

Answer 1

使用cook-levin定理的证明，对于每个输入 $ x $ 您可以在多项式时间中构造sat实例 $ \ phi（r，z）$ 哪个编码” $ m $ 在输入时$ x $ 和Randomnyness $ r $ “。这里 $ r $ 是 $ m=mathit {poly}（n）$ 比特的向量，表示 $ m $ ，而 $ z $ 是一个辅助矢量，具有以下属性：在任何接受run的 $ m $ 中，有一个设置的 $ z $ 满足<跨越类=“math-container”> $ \ phi $ 。

根据定义，如果 $ x \ in l $ 那么 $ \ phi $ 至少有< Span Class=“Math-Container”> $（2/3）2 ^ M $ 令人满意的分配，如果 $ x \ in notin l $ 那么< Span Class=“Math-Container”> $ \ Phi $ 最多 $（1/3）2 ^ m $ 令人满意的作业。您可以使用 $ \ mathsf {\＃sat} $ oracle来区分两种情况。