|
|||||
|
|
| 相对化概率算法类与非确定算法类的强分离 | |
| 引用本文： | 李祥.相对化概率算法类与非确定算法类的强分离[J].中国科学A辑,1992,35(12):1332-1340. |
| 作者姓名： | 李祥 |
| 作者单位： | 贵州大学计算机科学研究所 贵阳 550025 中国科学技术大学研究生院信息安全国家重点实验室,北京 100039 |
| 摘 要： | 本文提出并讨论了多项式时间概率型算法复杂度语言类与指数时间非确定型算法复杂度语言类的强分离(即带禁集证据的分离)问题,获得并证明了存在一个递归Oracle集A使得在多项式时间有界错误概率复杂度语言类BPPA中存在NEXTkA禁集,这里NEXTkA=∪NTIMEA(2cnk)表示计算时间限界于O(2nk)的指数时间非确定型算法所接受的语言类;我们指出,Oracle集A可以一致地对k构成并列举熟知的语言类P,NP,U,R,BPP,PP,∑2p,∏2p,Δ2p以及交互式证明系统语言类MA,AM,IP等之间的30余种强分离关系作为本文结果的直接推论. |
| 关 键 词： | 多项式时间概率算法 指数时间非确定型算法 禁集 相对化强分离 交互式证明系统 |
| 点击此处可从《中国科学A辑》浏览原始摘要信息 | |
| 点击此处可从《中国科学A辑》下载免费的PDF全文 | |