判定形式旅行商问题 (TSP) 属于 NPC 类证明

要证明判定形式旅行商问题 (Decision version of Traveling Salesman Problem, TSP) 属于 NPC 类，需要证明：

1. 判定形式 TSP 存在一个非确定性图灵机可以在多项式时间内解决。
2. 判定形式 TSP 可以用多项式时间归约到一个已知的 NPC 问题。

证明第一点：

假设有一个判定形式 TSP 问题实例，要求在给定的有向完全图中是否存在一个长度不超过 K 的哈密顿回路。

构造一个非确定性图灵机 M，M 的工作流程如下：

1. 非确定性地选择一个节点作为起点。
2. 从起点开始遍历图，每次选择一个未访问的相邻节点，直到遍历了所有节点，形成一条哈密顿回路。
3. 检查哈密顿回路的长度是否小于等于 K，如果是，则 M 接受输入，否则 M 拒绝输入。

由于 M 是非确定性图灵机，它可以在多项式时间内解决判定形式 TSP 问题实例。

证明第二点：

要证明判定形式 TSP 可以用多项式时间归约到一个已知的 NPC 问题，可以考虑将其归约到哈密顿回路问题。

假设有一个判定形式 TSP 问题实例，要求在给定的有向完全图中是否存在一个长度不超过 K 的哈密顿回路。

构造一个函数 f，将该问题归约到哈密顿回路问题。f 的工作流程如下：

1. 将判定形式 TSP 问题实例中的有向完全图 G 转化为无向完全图 G'。
2. 对 G' 中的每条边赋一个权值为 1。
3. 将 K 设为 G' 中节点数减 1。
4. 返回 G' 和 K。

可以证明，f 是一个多项式时间可计算的函数，并且 f 的输出可以在多项式时间内转化为哈密顿回路问题的输入。因此，可以将判定形式 TSP 问题归约到哈密顿回路问题，而哈密顿回路问题已知是 NPC 问题，因此判定形式 TSP 问题也属于 NPC 类。