无向可平面图哈密顿性的二次证明：P与NP的复杂性分析

本文《A Second Proof of the Conjecture that the Class P is a Proper Subset of the Class NP》由作者徐万东撰写，关注的是计算机科学中的一个重要理论争议：P与NP问题。P类问题是指可以在多项式时间内解决的问题，而NP类则包含那些虽然可能难以找到直接解，但验证一个潜在解却相对较快的问题。哈密顿图问题（Hamiltonian Cycle，HC）是一个经典的NP完全问题，即在给定的无向图中判断是否存在一条经过所有顶点恰好一次的路径。 作者针对判定无向可平面图是否为哈密顿图这一NP完全问题，提出了一个新的证明方法。他首先分析了HC问题的本质，利用必要且充分条件将问题转化为检查每个连通分量内是否存在特定禁止子图。这个转换使得判断是否存在无禁止子图可以在多项式时间内完成，但对于确认是否存在至少一个没有禁止子图的极大生成子图，其复杂度并非多项式，而是超多项式级别，具体时间复杂度为O(n^2^(1.5n)+Δ)，其中n为图的顶点数，Δ表示图的最大度数。 这个结果表明，尽管可以有效地检测是否存在禁止子图，但找到一个哈密顿回路（即满足条件的极大生成子图）的过程超越了P类的限制。因此，作者得出结论，哈密顿图问题属于NP类但不属于P类，进一步支持了P与NP之间存在严格包含关系的猜想。关键词包括P问题与NP问题、P类、NP类、哈密顿路径、哈密顿图、计算性以及计算复杂性。 通过这篇论文，徐万东不仅提供了一个新的角度来理解HC问题的困难，还深化了我们对P与NP复杂性界限的认识，这在理论计算机科学领域具有重要意义。对于研究人员和学生们来说，这篇文章提供了深入研究这两个复杂性类之间关系的重要参考材料。