对PP和BPP定义之间差异的具体理解

Question

我对如何 pp 和 BPP 定义。让我们假设$ chi $是语言$ mathcal {l} $的特征功能。 m 成为概率的图灵机。以下定义正确：
$ bpp = { mathcal {l}：pr [ chi（x） ne m（x）] geq frac {1} {2} {2} + epsilon epsilon quad forall x forall x in nathcal in mathcal {l} ， epsilon> 0 } $
$ pp = { mathcal {l}：pr [ chi（x） ne m（x）]> frac {1} {2} {2} } $

如果定义是错误的，请尝试进行最小的更改以使其正确（即不要给出其他使用计数计算机或一些修改模型的等效定义）。我无法正确区分两个定义的概率条件。

一些具体的例子对微妙的观点有清晰的见解将非常有帮助。

Answer 1

看上去对我来说是正确的。 BPP和PP之间的区别在于，对于BPP，概率必须大于$ 1/2 $ 通过常数, ，而对于PP，可能是$ 1/2+ 1/2^n $。因此，对于BPP问题，您可以通过少量重复进行概率放大，而对于一般PP问题，您不能进行。

Answer 2

VOR的答案给出了标准定义。让我尝试更直观地解释差异。

令$ m $为一种有界错误的概率概率多项式算法，对于语言$ l $，它以概率至少$ p geq frac {1} {2} {2}+ delta $正确答案。令$ x $为输入，而$ n $是输入的大小。

与$ mathsf {bpp} $算法有什么区别于任意$ mathsf {pp} $算法是 正差距 在接受l $中接受$ x 的概率与接受$ x notin l $的概率之间。 关于$ mathsf {bpp} $的基本要素是，差距至少为$ n^{ - o（1）} $。我将尝试解释为什么这种区别很重要，并允许我们考虑$ mathsf {bpp} $被视为有效算法（甚至指出等于$ m athsf {p} $），而$ mathsf {pp} $被认为效率低下（实际上$ Mathsf {pp} $包含$ mathsf {np} $）。所有这些都来自这个差距。

让我们从更仔细地查看$ mathsf {pp} $开始。

请注意，如果算法在执行过程中最多使用$ r（n）$随机位，并且错误概率小于$ 2^{ - r（n）} $，则错误概率实际上是$ 0 $，则不能选择任何选择随机位会使算法答案错误。

此外，具有运行时间$ t（n）$的算法不能使用超过$ t（n）$随机位，因此，如果概率算法的错误使用最差的运行时间$ t（n）$好于

有了类似的论点，我们可以证明，接受$ x in l $的概率与接受$ x notin l $的概率太小的情况与我们不一样的情况相似在$ Mathsf {pp} $ case中几乎没有区别。

现在，让我们转向$ Mathsf {BPP} $。

在概率算法中，我们可以提高正确答案的概率。假设我们希望将正确性概率提高到$ 1- epsilon $，以说明错误概率$ epsilon = 2^{ - n} $（指数为小错误）。

这个想法很简单：几次运行$ m $，并获得大多数人的答案。

我们应该运行多少次$ m $以使错误概率最多达到$ epsilon $？ $ theta（ delta^{ - 1} lg epsilon）$ times。证明在此答案的底部给出。

现在，让我们考虑一下我们正在讨论的算法是多项式时间。这意味着我们不能多次多次运行$ m $。换句话说，$ theta（ delta^{ - 1} ln epsilon）= n^{o（1）} $，或更多简单

$$ delta^{ - 1} lg epsilon = n^{o（1）} $$

这种关系将有限的错误概率算法分为类，具体取决于其错误概率。错误概率$ epsilon $是$ 2^{ - n} $或正常常数（即没有$ n $）或$ frac {1} {2} {2} -n^{{ o（1）} $。我们可以从其中一个到另一个，同时留在多项式时间内。

但是，如果$ delta $太小，例如$ 0 $，$ 2^{ - n} $，甚至$ n^{ - omega（1）} $，那么我们没有一种提高正确性概率和的方法足够降低错误概率以进入$ Mathsf {BPP} $。

这里的要点是，在$ mathsf {bpp} $中，我们可以有效地呈指数级的错误概率，因此我们几乎可以确定答案，这就是我们认为这类算法是有效算法的原因。误差概率可以降低，以至于硬件故障的可能性更大，甚至是流星掉落在计算机上的可能性比概率算法的错误更有可能。

对于$ mathsf {pp} $而言，这是不正确的，我们不知道有任何减少错误概率的方法 几乎 好像我们是通过扔硬币来获得答案来回答的（我们不是完全，概率不是一半，但与这种情况非常接近）。

---

本节给出了证明，当我们从gap $（ frac {1} {2} {2} - delta， frac {1} {2} {2}+ delta）开始时，要获得错误概率$ epsilon $。应该运行$ M $ $ theta（ delta^{ - 1} lg epsilon）$ times。

令$ n_k $为运行$ m $ $ k $ times的算法，然后根据多数的答案答案。为简单起见，假设$ k $很奇怪，所以我们没有关系。

考虑到l $中的$ x 的情况。 $ x notin l $相似。然后$$ MATHSF {pr} {m（x） text {ccepps} } = p geq frac {1} {2} {2} + delta $ $分析我们需要$ n_k $的正确性概率估计$ k $运行的大多数接受的可能性。

如果$ i $ th运行接受，则令$ x_i $为1，如果拒绝，则为$ 0 $。请注意，每次运行都独立于他人，因为他们使用独立的随机位。因此，$ x_i $ s是独立的布尔随机变量，其中$$ mathbb {e} [x_i] = mathsf {pr} {x_i = 1 } = mathsf {pr} } } = p geq frac {1} {2}+ delta $$

令$ y = sigma_ {i = 1}^k x_i $。我们需要估计多数接受的概率，即$ y geq frac {k} {2} $的可能性。

$ MATHSF {pr} {n_k（x） text {accepts} } = mathsf {pr} {y geq frac frac {k} {2} {2} } $$

怎么做？我们可以使用Chernoff Bound，告诉我们接近预期值的概率浓度。对于任何随机变量$ z $，带有预期值$ mu $，我们有

$$ mathsf {pr} {| z- mu | > alpha mu } <e^{ frac { alpha^2} {4} {4} mu} $$

这说明$ z $是$ alpha mu $远离其预期价值$ mu $的可能性，随着$ alpha $的增加而呈指数减少。我们将使用它来限制$ y < frac {k} {2} $的概率。

请注意，根据期望的线性性，我们有$$ mathbb {e} [y] = mathbb {e} [ sigma_ { sigma_ {i = 1}^k x_i] = sigma_ {i = 1}^k mathbb {e } [x_i] = kp geq frac {k} {2} + k delta $$

现在，我们可以应用Chernoff Bound。我们想要$ y < frac {k} {2} $的概率上限。 Chernoff Bound将在$ | y - （ frac {k} {2} {2}+k delta）的概率上给出上限。 > k delta $足够。我们有

$$ pr {| y -kp | > alpha kp } <e^{ - frac { alpha^2} {4} kp} $$

如果我们选择$ alpha $，以便$ alpha kp = k delta $我们完成了，所以我们选择$ alpha = frac { delta} {p} {p} leq leq frac {2 delta} {2 delta} {2 delta+1} $。

因此我们有

$$ pr {y < frac {k} {2} } leq pr {| y - （ frac {k} {2} {2}+k delta）| > k delta } leq pr {| y -kp | > alpha kp } <e^{ - frac { alpha^2} {4} kp} $$

如果您进行计算，您会发现

$$ frac { alpha^2} {4} kp leq frac { delta^2} {4 delta+2} k = theta（k delta）$$

我们有

$$ pr {y < frac {k} {2} } <e^{ - theta（k delta）} $$

我们希望错误最多是$ epsilon $，所以我们想要

$$ e^{ - theta（k delta）} leq epsilon $$

换句话说

$$ theta（ delta^{ - 1} lg epsilon） leq k $$

重要的一点是，在此过程中，我们将使用更多的随机位，并且运行时间也会增加，即$ n_k $的最差运行时间将大约是$ k $ k $ timples的运行时间$ M的运行时间$。

这里的间隙是$ frac {1} {2} $。但总的来说，情况并非如此。我们可以通过将其他分数代替多数占用来采用类似的方法。

Answer 3

使用您的符号：

$ bpp = {l：存在$ a概率多项式的图灵机$ m，$和costant $ 0 <c leq 1/2 $，这样$ forall x ; pr [ chi_l（x）= m（x）] geq frac {1} {2} {2} + c } $

$ pp = {l：存在$ a概率的多项式图灵机$ m $，这样$ forall x ; pr [ chi_l（x）= m（x）]> frac {1} {2} } $

艾德里安（Adriann）指出了区别，您也可以看一下Wikipedia PP与BPP