\(\S\) 结论
TSP问题：n阶带权无向完全图中，找权值最小的哈密顿回路（无向图中遍历所有顶点的回路）
优化问题，记最优解为OPT
对于一般的n顶点TSP问题（非Metric），任意 多项式时间内可计算的函数f(n) 均不可近似，除非P = NP
已知 哈密顿回路存在性判定 是经典的NPC问题；f(n)举例：\(f(n) = 2^n\)
\(\S\) 证明
思路
去证假设有那么个f(n)的近似比存在，则可在多项式时间内求解哈密顿回路这个NPC问题，则P = NP
具体过程
（从NPC问题实例出发归约到TSP问题）
对于一个n顶点哈密顿回路的实例，我们在此基础上构造一张完全图：
- 对于原实例图中已有的边，定义权重为\(1\)
- 对于原实例图中没有的边，定义权重为\(nf(n)\) （\(f(n)\)多项式时间内可计算，且因为是近似比，\(f(n)>1\)）
构造的新图即为n顶点的TSP问题。则对于新图，可分析：
- 原实例图存在哈密顿回路 \(\Leftrightarrow\) 新图中至少有那个哈密顿回路，且必然权重最小，所以\(OPT = n\)；
- 原实例图没有哈密顿回路 \(\Leftrightarrow\) 新图必然要用到新加的权重为\(nf(n)\)的边，所以\(OPT > nf(n)\);
NPC问题归约后的两种情况出现了Gap，且这个Gap无法被近似比逾越！
那如果n顶点TSP问题有某个 近似比为f(n) 的近似算法，那不妨对新图使用该算法：
- 若\(OPT = n\)，则根据定义，得到的解 \(cost \leq nf(n)\)
- 若\(OPT > nf(n)\)，则得到的解 \(cost > OPT > nf(n)\)
由于不存在其他的OPT情况(有Gap)，所以反向推导也成立。即我们可以通过该近似算法，在多项式时间内判断原实例图是否存在哈密顿回路，即解决了NPC问题，即P = NP
得证
标签：OPT,哈密顿,不可,近似,nf,实例,回路,TSP From： https://www.cnblogs.com/elucidator-xrb/p/17450473.html