一个 NP-完全问题的求解复杂性剖析

本文提出一个构造的ＮＰ完全问题ＲＨＣ并证明其ＮＰ完全性。在此基础上,通过分析通用图灵机带头移动的次数,讨论了通用图灵机上任一求解ＲＨＣ的算法的复杂性。分析结果揭示了在简单计算模型（定义见正文）上寻找一个对满足ＲＨＣ的任意输入,而不是对某些特殊实例都能正确求解的算法的困难性。根据本文的讨论,我们认为,给出本文分析的严格论证或许只是时间问题。