| 一个 NP-完全问题的求解复杂性剖析 |
| |
| 引用本文： | 姜新文,王兵山.一个 NP-完全问题的求解复杂性剖析[J].国防科技大学学报,1994,16(1):45-52. |
| |
| 作者姓名： | 姜新文 王兵山 |
| |
| 作者单位： | 国防科技大学电子计算机系 |
| |
| 摘 要： | 本文提出一个构造的ＮＰ完全问题ＲＨＣ并证明其ＮＰ完全性。在此基础上，通过分析通用图灵机带头移动的次数，讨论了通用图灵机上任一求解ＲＨＣ的算法的复杂性。分析结果揭示了在简单计算模型（定义见正文）上寻找一个对满足ＲＨＣ的任意输入，而不是对某些特殊实例都能正确求解的算法的困难性。根据本文的讨论，我们认为，给出本文分析的严格论证或许只是时间问题。
|
| 关 键 词： | 复杂性，算法，NP问题，NP─完全问题 |
| 收稿时间： | 1992/11/23 0:00:00 |
Analysing the complexity of A NP-complete problem |
| |
| Jiang Xinwen and Wang Bingshan.Analysing the complexity of A NP-complete problem[J].Journal of National University of Defense Technology,1994,16(1):45-52. |
| |
| Authors: | Jiang Xinwen and Wang Bingshan |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《国防科技大学学报》浏览原始摘要信息 |
| 点击此处可从《国防科技大学学报》下载免费的PDF全文 |
