跳到主要内容

概率 Turing 机

阐述

是非确定性 Turing 机的一种,其中每个非确定性的步骤具有两个可能的等概率分叉。因此该机器中一个分支的概率是

Pr[b]=2k\operatorname{Pr}[b]=2^{-k}

定义 MM 接受 ww 的概率为

Pr[M accepts w]=Pr[b]\operatorname{Pr}[M \text { accepts } w]=\sum \operatorname{Pr}[b]

MM 以误差 ε\varepsilon 判定语言 AA,如果

  1. wA implies Pr[M accepts w]1ϵw \in A \text { implies } \operatorname{Pr}[M \text { accepts } w] \geq 1-\epsilon
  2. wA implies Pr[M rejects w]1ϵw \notin A \text { implies } \operatorname{Pr}[M \text { rejects } w] \geq 1-\epsilon

放大引理

这种误差可以被放大引理进一步缩小。设 0<ε<1/20<\varepsilon<1/2,对于任何多项式 p(n)p(n),如果存在一个误差为 ε\varepsilon 的概率多项式 Turing 机 M1M_1,那么也存在一个误差为 2p(n)2^{-p(n)}M2M_2

能在概率 Turing 机上以多项式时间解决的问题称为 BPP 复杂度类

实例

性质

相关内容

参考文献