| P≠NP假设下NP-NPC-P中自然问题的一个候选者 |
| |
| 引用本文： | 赵运磊,朱洪.P≠NP假设下NP-NPC-P中自然问题的一个候选者[J].软件学报,2001,12(5):656-658. |
| |
| 作者姓名： | 赵运磊 朱洪 |
| |
| 作者单位： | 复旦大学计算机科学系, |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under G rant No.69973013 (国家自然科学基金) |
| |
| 摘 要： | 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.
|
| 关 键 词： | NP-Complete Karp-归约 SAT NPI |
| 文章编号： | 1000-9825/2001/12(05)0656-03 |
| 收稿时间： | 2000/5/22 0:00:00 |
| 修稿时间： | 2000年5月22日 |
Candidate for Natural Problems in NP-NPC-P under P |
| |
| ZHAO Yun lei and ZHU Hong.Candidate for Natural Problems in NP-NPC-P under P[J].Journal of Software,2001,12(5):656-658. |
| |
| Authors: | ZHAO Yun lei and ZHU Hong |
| |
| Abstract: | |
| |
| Keywords: | NP complete Karp reduction SAT NPI |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
