Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 可计算性简明纲要(13)
发信站: 哈工大紫丁香 (2001年06月14日15:44:49 星期四), 站内信件

第五节 算法复杂度类
说明 下面把判定问题简称为问题.
定义 一个问题属于ZPP,iff 存在一个时间复杂度的数学期望为
多项式的随机化算法,无论正确结果如何,该算法算错的概率为0.
定义 一个问题属于RP, iff 存在一个最坏为多项式时间的随机
化算法,当正确结果为1时,算法错误概率小于0.5;正确结果为0
时,算法错误概率为0.
定义 一个问题属于BPP, iff 存在一个最坏为多项式时间的随机
化算法,无论正确结果如何,该算法算错的概率小于0.25.
定义 一个问题属于co-NP, iff 它的补属于NP.
定理 P是ZPP的子集;ZPP是RP的子集;RP是BPP的子集.BPP是NP的
子集.
定理 P是NP和co-NP的交集的子集.
定理 NP=PSPACE.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]