将TSP降低到哈密顿电路

Question

如何将旅行商问题的(决定版本)转换为哈密尔顿电路问题(即如何将TSP降低到HCP,如果我有HCP解决方案,那么我将使用该解决方案来解决TSP问题)？

Answer 1

NP中的每个问题都可以是多项式时间减少到任何NP完全问题 - 这就是NP完全问题如此重要的原因.

这是一系列减少:

1. 顶点盖可以缩减为哈密顿电路.
2. 3-SAT可以缩减为Vertex Cover.
3. 可满足性可降至3-SAT.
4. NP中的任何决策问题都可以降低到可满足性(Cook-Levin定理)

TSP是NP中的一个问题,因此它可以在可笑的长多项式时间内减少到哈密顿电路.

我得到了计算机和难以理解的减少:NP完全性理论指南