证明 HAM-CYCLE 到 TSP 的归约是多项式时间？
Prove that the reduction of HAM-CYCLE to TSP is polynomial-time?
这是教授昨天上传的题目，准备明天的考试。我的问题是 b 部分（下面以粗体显示）；我不确定我应该做什么。
The Traveling Salesman Problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one (e.g. the hometown) and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip.
TSP = {(G, f, t): G = (V, E) a complete graph, f is a function V×V → Z, t ∈ Z, G is a graph that contains a traveling salesman tour with cost that does not exceed t}.
Let the HAM-CYCLE problem defined as follows: given an undirected graph G = (V, E), does there exist a simple cycle H that contains every node in V.
Let a complete graph be a graph where there is an edge “between” every possible tuple of vertices.
a-Define a certificate for TSP. Show that we can verify the certificate in deterministic polynomial time.
b-Prove that the reduction of HAM-CYCLE to TSP is polynomial-time.
c-Using the fact that HAM-CYCLE is NP-complete, what can we conclude?
正如您介绍的那样，TSP 和 HAM-CYCLE 之间只有三个区别：
- TSP 假设一个完整的图，而 HAM-CYCLE 允许一些顶点对不共享一条边。
- TSP 为每条边分配一个成本，而 HAM-CYCLE 将所有边视为等价的。
- TSP 寻求费用低于 t 的游览，而 HAM-CYCLE 接受任何游览。
给定一个图G和一个求解TSP的算法，我们可以如下求解HAM-CYCLE：
- 用与G.
相同的顶点集构造一个完整的图G′
- 设 f（我们的 TSP 成本函数）return 0 只要两个顶点在 G 中相邻，1每当他们不在的时候。
- 将我们的 TSP 求解算法应用于 (G′, f, t = 0), 和 return 结果。这将发现是否存在 G′ 的游览仅使用其对应物存在于 G.
中的边
以上是从 HAM-CYCLE 到 TSP 的多项式时间缩减。 （你明白为什么了吗？）
这是教授昨天上传的题目，准备明天的考试。我的问题是 b 部分（下面以粗体显示）；我不确定我应该做什么。
The Traveling Salesman Problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one (e.g. the hometown) and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip.
TSP = {(G, f, t): G = (V, E) a complete graph, f is a function V×V → Z, t ∈ Z, G is a graph that contains a traveling salesman tour with cost that does not exceed t}.
Let the HAM-CYCLE problem defined as follows: given an undirected graph G = (V, E), does there exist a simple cycle H that contains every node in V.
Let a complete graph be a graph where there is an edge “between” every possible tuple of vertices.
a-Define a certificate for TSP. Show that we can verify the certificate in deterministic polynomial time.
b-Prove that the reduction of HAM-CYCLE to TSP is polynomial-time.
c-Using the fact that HAM-CYCLE is NP-complete, what can we conclude?
正如您介绍的那样，TSP 和 HAM-CYCLE 之间只有三个区别：
- TSP 假设一个完整的图，而 HAM-CYCLE 允许一些顶点对不共享一条边。
- TSP 为每条边分配一个成本，而 HAM-CYCLE 将所有边视为等价的。
- TSP 寻求费用低于 t 的游览，而 HAM-CYCLE 接受任何游览。
给定一个图G和一个求解TSP的算法，我们可以如下求解HAM-CYCLE：
- 用与G. 相同的顶点集构造一个完整的图G′
- 设 f（我们的 TSP 成本函数）return 0 只要两个顶点在 G 中相邻，1每当他们不在的时候。
- 将我们的 TSP 求解算法应用于 (G′, f, t = 0), 和 return 结果。这将发现是否存在 G′ 的游览仅使用其对应物存在于 G. 中的边
以上是从 HAM-CYCLE 到 TSP 的多项式时间缩减。 （你明白为什么了吗？）