NP对PP

• 作者: 朱洪 赵一鸣 赵运磊
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: NP PP PCP 随机计算 复杂性理论
• 年，卷（期）: 2001,（7）
• 页码范围: 967-970
• 页数: 4页
• 分类号: TP301
• 字数: 1117字
• 语种: 中文

摘要

主要目的是研究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))的猜想.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵一鸣	复旦大学计算机科学系	59	353	8.0	17.0
2	朱洪	复旦大学计算机科学系	29	159	7.0	12.0
3	赵运磊	复旦大学计算机科学系	10	36	3.0	6.0