一个构造的Np完全问题及其复杂性下界猜测

摘要

本文提出一个构造的 Np 全全问题 DHC。该问题由(?)郎担问题和哈密顿回路判定问题导出,导出 DHC 的基本思想是试图使求解与 DHC 相应的最优化问题必须与输入无关地在图 G 的全部 H 回路间进行,从而使求解该最优化问题的算法的复杂性至少与图 G 中包含的哈密顿回路(即 H 回路)的条数有相同的数量级。根据 DHC 同与之相应的最优化问题的 Np 等价性(见定理2、定理3)可推断求解 DHC 的任何解定型算法的时间复杂性下界,按照本文的思想,不难构造出一大批类似的 Np 完全问题。本文提出的猜测,可能是对近来由于六大难题之一的子图同胚问题获得解决,更多的人开始由以前的试图证明 Np(?)P 转而考虑 Np=P 的反动。