P≠NP假设下NP-NPC-P中自然问题的一个候选者

• 作者: 朱洪 赵运磊
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: NP-Complete Karp-归约 SAT NPI
• 年，卷（期）: 2001,（5）
• 页码范围: 656-658
• 页数: 3页
• 分类号: TP301
• 字数: 520字
• 语种: 中文

摘要

1975年,Lander证明在P≠NP假设下存在一个语言属于NP-NPC-P(NPI).但Lander给出语言并不是一个自然的语言因在该语言的构造中需运行所有多项式时间的图灵机.迄今为止,还没有自然的语言被证明在P≠NP假设下属于NPI,并且在P≠NP假设下寻找一个属于NPI的自然语言是一个重要的未解决问题.作者部分解决了此长期未解决的问题.定义了2+f(m)-HAST模型.基于该模型，给出了在P≠NP假设下NP-NPC-P中自然问题的一个候选者.已证明在P≠NP 假设下它不属于NPC并且在更强但合理的假设下它的确属于NPI.

作者信息

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