| 关于相对化的P=?NP问题的注记 |
| |
| 引用本文： | 宋恩民,金人超,黄文奇.关于相对化的P=?NP问题的注记[J].数学研究及应用,1993,13(3):443-450. |
| |
| 作者姓名： | 宋恩民 金人超 黄文奇 |
| |
| 作者单位： | 华中理工大学计算机系;华中理工大学计算机系;华中理工大学计算机系 |
| |
| 基金项目： | 国家自然科学基金资助项目. |
| |
| 摘 要： | 问题P=?NP在相对化后随外部信息集的不同可能有相反的答案.本文得出如下进一步的结果:1.存在着无穷个集合S1,S2,…,这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能交替地使命题P=NP和P≠NP,相对比;2.存在着在NP类之外的递归集A,使得P=NP等价于PA=NPA.
|
| 关 键 词： | NP问题 计算机科学 相对可比定理 |
| 收稿时间： | 1991/3/11 0:00:00 |
Note on the P =?NP Problem Relativized |
| |
| Song Enmin,Jin Renchao and Huang Wenqi.Note on the P =?NP Problem Relativized[J].Journal of Mathematical Research with Applications,1993,13(3):443-450. |
| |
| Authors: | Song Enmin Jin Renchao and Huang Wenqi |
| |
| Institution: | Dept. of Computer; Huazhong Univ. of Scie. and Tech.; Wuhan;Dept. of Computer; Huazhong Univ. of Scie. and Tech.; Wuhan;Dept. of Computer; Huazhong Univ. of Scie. and Tech.; Wuhan |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
| 点击此处可从《数学研究及应用》下载免费的PDF全文 |
|
