概率复杂性类/ probabilistic complexity class // probabilistic complexity class /
概率复杂性类是概率图灵机解决的判定问题类。
单侧错误随机多项式时间RP类/ one-sided error randomized polynomial-time /one-sided error randomized polynomial-time
概率复杂性类随机算法以单侧错误方式有效求解的问题类。有界错误概率多项式时间BPP类/ bounded error probabilistic polynomial time class BPP /bounded error probabilistic polynomial time class BPP
概率复杂性类BPP类是用随机算法（或概率图灵机）能够有效求解的问题类。零错误概率多项式时间ZPP类/ Zero-error probabilistic polynomial-time /Zero-error probabilistic polynomial-time
概率复杂性类一个语言L属于零错误概率多项式时间（Zero-error Probabilistic Polynomial-time）ZPP类，当且仅当存在着一个对于所有输入都给出正确答案的随机算法，该随机算法在每个输入上的期望运行时间是多项式时间的。
京公网安备 11010202008139号