概率Turning机与随机复杂性类

【概率图灵机】
概率图灵机（简称PTM）是一台总停机的NTM，每个格局至多有2个后继，这样的格局称为随机格局。PTM停机时，除了接受状态和拒绝状态，还有一种未知状态，此时称此计算为无效计算。
对于输入x，设c是关于x的一个计算，c有k个随机格局，则定义计算c的概率为\(2^{-k}\). 定义接受x的概率为所有接受x的计算的概率之和，记作\(\alpha(U,x)\). 类似定义拒绝x的概率、计算无效的概率为\(\beta(U,x),\gamma(U,x)\).
我们有：\(\alpha(U,x)+\beta(U,x)+\gamma(U,x)=1.\)

【PP机与PP类】
如果某PTM是多项式时间界限，且没有未知状态，则称为PP机。
对于输入x，恒有：\(\alpha(U,x)+\beta(U,x)=1.\)
PP机接受的语言全体称为PP类。

PP机U对输入x的错误概率记为\(err(U,x).\)
当\(x\in L(U)\)时，\(err(U,x)\)即为U将x误给出“不接受”状态的概率，故\(err(U,x)=\beta(U,x).\)
同理，当\(x\notin L(U)\)时，\(err(U,x)=\alpha(U,x).\)

定理1. \(PP\subseteq PSPACE.\)
用多项式空间界限的DTM模拟PP机运算，在模拟输入x的每一个计算时，同时检查这个计算有多少个随机格局。若U是\(n^k\)单位界限的，则概率最小单位是\(2^{-n^k}\).

引理2. \(L\in PP \Leftrightarrow \exists PP:U,\) \(\forall x, \alpha(U,x)\ge \frac 1 2\rightarrow x\in L;\beta(U,x)> \frac 1 2\rightarrow x\notin L.\)
引理2说明了PP类与coPP类的关系。这证明了：
定理3. PP类在补运算下封闭。

定理4.\(NP\cup coNP \subseteq PP.\)
用PP机\(U_2\)模拟NTM\(U_1\)的运算，在NTM计算树的根节点上，添加一PP机的根节点，并将其作为左后继；其右后继为一树叶，且为接受格局。因此，\(x\in L(U_1)\Leftrightarrow \alpha (U_2,x) > \frac 1 2\Leftrightarrow x\in L(U_2).\)

【BPP机与BPP类】
对于某台PP机，如果存在\(\epsilon \in (0,\frac 1 2 )\)使得对所有的输入x，均有\(\alpha(U,x) > \frac 1 2 + \epsilon \lor \beta ( U,x ) > \frac 1 2 +\epsilon.\)称其为一台BPP机。BPP机接受的语言全体称作BPP类。

定理5. 设U是BPP机，q是一个恒正整系数多项式。则存在PP机\(U_0\)使得对每个输入\(x,|x|=n,\) 有\(x\in L(U)\)时\(\alpha(U_0,x) > 1 - 2 ^{-q(n)}\); 否则\(\beta(U_0,x) > 1 - 2 ^{-q(n)}\).

推论6. 设\(L\in BPP,\epsilon \in (0,\frac 1 2 ).\)则存在BPP机U接受L，且对每个输入x，有\(err(U,x) < \epsilon.\)

【RP机与RP类】
对于某个PP机，若对每个输入x，要么\(\alpha(U,x) > \frac 1 2\), 要么\(\beta(U,x)=0.\) 称其为一台RP机。
定义指出，如果U不接受输入x，则一定回答拒绝；如果U接受x，则可能回答接受也可能不接受，且接受的概率大于\(\frac 1 2.\)

定理7. \(RP \cup coRP \subseteq BRR.\)
BPP在补运算下封闭，只需证明RP。构造一台BPP机模拟某RP机运算两次，只要有一次接受就也接受，则二者接受语言相同，且接受时\(\alpha(U_0,x)\ge \frac 3 4,\) 拒绝时\(\beta(U_0,x)=1.\)
采用重复运算的策略，也可以加强RP机的定义，将\(\frac 1 2\)提高到任意小于1的常数。

定理8. \(RP \subseteq NP.\)
证明的关键在于\(x\notin L(U)\Rightarrow \beta(U,x)=0.\)回顾NTM关于接受的定义，只要有一个计算接受x，则此NTM接受x。而RP机不可能出现本不接受而误答接受的情况。

【ZPP机与ZPP类】
对于某个多项式时间界限的PTM，如果对每个输入x，要么\(\alpha(U,x) > \frac 1 2\land\beta(U,x)=0\), 要么\(\beta(U,x) > \frac 1 2\land\alpha(U,x)=0\)，称为一台ZPP机。
注意，ZPP机可以有未知接受状态，所以ZPP机不一定是PP机。另外，如果ZPP机给出了明确回答，就一定是正确答案（接受/不接受），且无效计算的概率小于\(frac 1 2.\) 同样地，采取重复计算的方法，可以将无效计算的概率降低到任意小的正常数。

定理9. \(P \subseteq ZPP.\)
只需将多项式时间的DTM看作PTM，则\(\alpha=1\lor \beta=1.\)

定理10. \(ZPP=RP \cap coRP.\)
如果将ZPP机的未知状态视为接受状态，它就是一台RP机。故\(ZPP\subset RP.\) 由接受/不接受状态的对称性，ZPP类在补运算下封闭。故 \(ZPP\subseteq RP \cap coRP.\)
另一方面，对于\(L \in RP \cap coRP\)，构造两个RP机分别模拟\(L,\overline L.\) 对同一个输入，至多一台给出接受状态。于是，可用一台PTM模拟此二RP机的运算，则为一台ZPP机。故 \(ZPP\supseteq RP \cap coRP.\)

    所属分类：TCS     发表于2022-01-02