| NP对PP |
| |
| 引用本文： | 赵运磊,朱洪,赵一鸣.NP对PP[J].软件学报,2001,12(7):967-970. |
| |
| 作者姓名： | 赵运磊 朱洪 赵一鸣 |
| |
| 作者单位： | 复旦大学计算机科学系, |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant No.69973013 (国家自然科学基金) |
| |
| 摘 要： | 主要目的是研究NP与PP的关系。引入了一个NP的等价的随机定义。基于此等价定义，定义了另一个随机复杂性类：SUPER－NP。虽然SUPER－NP与NP非常接近，但令人吃惊的是发现了PP包含于SUPER－NP，从而NP包含于PP包含于SUPER－NP。考虑到NP＝PCP（log,O(1))以及NP和SUPER－NP的相似性，也希望能通过证明SUPER－NP包含于PCP（log^2,O(1))来解决PP包含于PCP（log^2,O(1))的猜想。
|
| 关 键 词： | NP PP PCP 随机计算 复杂性理论 |
| 文章编号： | 1000-9825200112(07)0967-04 |
| 收稿时间： | 2000/10/23 0:00:00 |
| 修稿时间： | 2000年10月23 |
NP Versus PP |
| |
| ZHAO Yun lei,ZHU Hong and ZHAO Yi ming.NP Versus PP[J].Journal of Software,2001,12(7):967-970. |
| |
| Authors: | ZHAO Yun lei ZHU Hong and ZHAO Yi ming |
| |
| Abstract: | In this paper, the authors mainly intend to clarify the relation between NP and PP . A randomized version of NP is given. Based on this equivalent definition of NP , another randomized complexity class is given: SUPER-NP . Although the SUPER-NP is very close to NP , but it is found surprisingly that PP?SUPER NP and thus NP?PP?SUPER-NP . In light of NP=PCP(log, O(1)) and the closeness of NP and SUPER-NP it is hoped that PP?PCP(log2,O(1)) conjecture can be peoved by showing that SUPER-NP?PCP(log2,O(1)). |
| |
| Keywords: | NP PP PCP randomized computation complexity theory |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
