| 引用本文: | 姜新文,王兵山.一个 NP-完全问题的求解复杂性剖析.[J].国防科技大学学报,1994,16(1):45-52.[点击复制] |
| Jiang Xinwen,Wang Bingshan.Analysing the complexity of A NP-complete problem[J].Journal of National University of Defense Technology,1994,16(1):45-52[点击复制] |
|
| |
|
|
| 本文已被：浏览 7505次 下载 6680次 |
| 一个 NP-完全问题的求解复杂性剖析 |
| 姜新文, 王兵山 |
|
(国防科技大学 电子计算机系 湖南 长沙 410073)
|
| 摘要: |
| 本文提出一个构造的 NP 完全问题 RHC 并证明其 NP完全性。在此基础上，通过分析通用图灵机带头移动的次数，讨论了通用图灵机上任一求解 RHC 的算法的复杂性。分析结果揭示了在简单计算模型(定义见正文)上寻找一个对满足 RHC 的任意输入，而不是对某些特殊实例都能正确求解的算法的困难性。根据本文的讨论，我们认为，给出本文分析的严格论证或许只是时间问题。 |
| 关键词: 复杂性，算法，NP 问题，NP-完全问题 |
| DOI： |
| 投稿日期：1992-11-23 |
| 基金项目: |
|
| Analysing the complexity of A NP-complete problem |
| Jiang Xinwen, Wang Bingshan |
|
(Department of Computer Science，NUDT，Changsha 410073)
|
| Abstract: |
| We introduce a NP-complete problem named RHC and prove its NP-complete property in this paper. Secondly，we discuss the complexity any algorithm solving RHC presents by counting the moving times of the tape head on turning machine. The conclution drawn from our analysis shows at least that it is difficult to find an algorithm to solve RHC though the analysis is not a mathematical one, Hence，maybe it needs only time we think，to confirm the analysis. |
| Keywords: complexity,algorithm,NP problem NP-complete problem |
|
|
