我试图理解 NP Complete 的正式定义并且有一些问题。我想知道是否有人可以提供更多见解。
Jon Kleinberg 算法书说，如果每个 NP 问题都可以简化为问题 X，那么问题 X 在集合 NP Complete 中。
现在由于 P 是 NP 的子集，因此我们可以在多项式时间内将 P 中的任何问题简化为 NP 完全问题。这导致了一个矛盾，因为减少是在多项式时间内，我们可以在多项式时间内解决这个 NP 完全问题。这不可能是真的。所以我不确定这个推理在哪里是错误的。
此外，如果我们能够将多项式时间内的任何 NP 问题简化为 NP Complete，那么为什么我们说 NP Complete 更难。由于减少是多项式时间，渐近地说，它不应该有所作为。
现在由于 P 是 NP 的子集，因此我们可以在多项式时间内将 P 中的任何问题简化为 NP 完全问题。这导致了一个矛盾，因为减少是在多项式时间内，我们可以在多项式时间内解决这个 NP 完全问题。
你把减少的方向弄错了。如果您可以将任何 NP 完全问题简化为给定的 P 问题，则 P = NP，因为这意味着该 P 问题比任何 NP 完全问题更难或等价。一个 P 问题可以简化为 NP 问题这一事实并不表明它比 NP 更难——它表明它比 NP 更容易，这并不奇怪或矛盾。
假设我们可以将最短路径减少到 1 次运行 TSP，并假设 TSP 只能通过枚举来解决（指数复杂度）。那么，最短路径是多项式的，归约是多项式的（O(1)），但 TSP 不是多项式的。这是一个假设的例子。但希望它表明 TSP 可以一次性解决 SP 的事实并不意味着 TSP 无论如何都很容易。TSP 的复杂性不受它可以轻松解决 SP 的事实的限制。