如果找到一个 NP-Complete 问题的多项式时间算法，这是否意味着它对所有 NP 问题都是相同的时间复杂度？
If a polynomial time algorithm for an NP-Complete problem is found, does this imply that it is the same time complexity for all NP problems?
如果找到一个 NP 完全问题的多项式时间算法，假设它的 O(n^2)，这是否意味着所有 NP 问题都有一个 O(n^2) 的解决方案？我知道这意味着所有 NP 问题都有一个多项式解，但它一定是 O(n^2) 吗？
不一定
A problem x that is in NP is also in NP-Complete if and only if every
other problem in NP can be quickly (ie. in polynomial time)
transformed into x.
因此，解决一个 NP 完全问题的算法意味着我们可以解决 NP 中的任何其他问题，方法是将其转换为该问题的实例并解决它。但是变换可以是任何复杂度，只要它的多项式满足条件即可。
所以你的问题的答案是否定的，一个O(N^2)算法来解决一个NP-Complete问题并不意味着所有的NP问题都可以在O(N^2)时间内解决，它只保证存在一个多项式时间算法来解决它。
即 O(N^2) + T(N) 其中 T(N) 是转换问题实例的复杂度
如果找到一个 NP 完全问题的多项式时间算法，假设它的 O(n^2)，这是否意味着所有 NP 问题都有一个 O(n^2) 的解决方案？我知道这意味着所有 NP 问题都有一个多项式解，但它一定是 O(n^2) 吗？
不一定
A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.
因此，解决一个 NP 完全问题的算法意味着我们可以解决 NP 中的任何其他问题，方法是将其转换为该问题的实例并解决它。但是变换可以是任何复杂度，只要它的多项式满足条件即可。
所以你的问题的答案是否定的，一个O(N^2)算法来解决一个NP-Complete问题并不意味着所有的NP问题都可以在O(N^2)时间内解决，它只保证存在一个多项式时间算法来解决它。
即 O(N^2) + T(N) 其中 T(N) 是转换问题实例的复杂度