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

证明：

首先，证明判定形式旅行商问题（Decision TSP）属于NP类：

一个问题属于NP类，当且仅当可以用一个非确定性图灵机在多项式时间内验证一个解是否正确。对于判定形式旅行商问题，可以给出一个非确定性图灵机，它可以在多项式时间内验证一个解是否正确。具体地，非确定性图灵机可以按照解给出的顺序检查每条边是否在图中，然后检查该解的边是否构成了一条哈密顿回路，即是否覆盖了所有的点。因此，判定形式旅行商问题属于NP类。

其次，证明判定形式旅行商问题是NP完全问题：

为了证明判定形式旅行商问题是NP完全问题，需要证明它是NP问题中最难的问题之一，即所有NP问题都能够在多项式时间内归约到判定形式旅行商问题。具体地，需要证明存在一个多项式时间的归约函数，将任何一个NP问题实例归约为一个判定形式旅行商问题实例，并保持问题的答案不变。

考虑一个任意的NP问题实例，可以用一个非确定性图灵机在多项式时间内验证一个解是否正确。将该问题实例转化为一个图，每个顶点代表一个可能的解，如果一个解可以被验证为正确，则在该顶点处放置一个标记，否则不放置标记。对于每对顶点，如果它们对应的解可以通过一个非确定性转移从一个解到达另一个解，则在它们之间连一条无向边，边权为0。对于没有边连接的顶点对，也需要在它们之间连一条无向边，边权为1。这样构造的图具有以下性质：

如果NP问题的答案是'是'，则至少有一个解被标记，即至少存在一个哈密顿回路。因此，该图存在一个哈密顿回路，其边权和为0。
如果NP问题的答案是'否'，则不存在任何解被标记。因此，该图不存在哈密顿回路，任何哈密顿回路的边权和都大于0。

因此，可以将该NP问题实例归约为一个判定形式旅行商问题实例，即在该图上求解最小哈密顿回路问题。由于该归约函数可以在多项式时间内完成，因此判定形式旅行商问题是NP完全问题。