| 摘要: |
| 主要目的是研究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(log2,O(1))来解决PP?PCP(log2,O(1))的猜想. |
| 关键词: NP PP PCP 随机计算 复杂性理论 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.69973013 (国家自然科学基金) |
|
| NP Versus PP |
|
ZHAO Yun lei,ZHU Hong,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)). |
| Key words: NP PP PCP randomized computation complexity theory |
