概率复杂性类

概率复杂性类（probabilistic complexity class），理学-计算机科学技术-计算机科学理论-计算复杂性-复杂性类-概率复杂性类，概率复杂性类是概率图灵机解决的判定问题类。概率图灵机概率图灵机与非确定型图灵机一样，每个格局可能有多个后继格局。非确定图灵机非确定地选择一个后续格局，概率图灵机则根据一个概率分布来选择后续格局。概率图灵机要有一个随机数源，通常是抛掷一枚均匀硬币，也可以是从一个预先准备好的随机数串中读取一位。概率图灵机通常根据得到的随机数以等概率选择一个后续格局，概率图灵机接受输入的概率等于所有接受计算分支的概率之和，拒绝输入的概率等于所有拒绝计算分支的概率之和。概率图灵机的错误概率等于所有给出错误答案的计算分支的概率之和。概率图灵机的运行时间是所有计算分支的最长运行时间，运行空间是所有计算分支的最大运行空间。