为什么说旅行商问题是NP Hard的？

Question

为什么说旅行商问题是NP Hard的？网上看了很多文章还是比较迷糊，有谁能清晰地讲解下。怎么样判断一个算法是不是NP Hard？

Answer 1

怎样证明一个问题C是NP完全问题呢？首先，要证明C是NP问题，也就是C的解的正确性容易验证；然后要证明有一个NP完全问题B，能够在多项式时间内归约到C。这就要求必须先存在至少一个NPC问题。Cook证明了NP完全问题的祖先就是SAT。SAT问题是指给定一个包含n个布尔变量的逻辑式，问是否存在一个取值组合，使得该式被满足。Cook证明了SAT是一个NPC问题，如果SAT容易解决，那么所有NP都容易解决。