如果找到了用于NP完全问题的多项式时间算法，则假设其O（n ^ 2），这是否意味着所有NP问题都有O（n ^ 2）解？我知道这意味着所有NP问题都有一个多项式解，但是必然是O（n ^ 2）吗？
不一定
NP中的问题x在且仅当每个 NP中的其他问题很快就会出现（即多项式时间） 转换为x。
因此，解决一个NP完全问题的算法意味着我们可以通过将NP转化为该问题的实例并对其进行求解来解决NP中的任何其他问题。但是，只要我们满足多项式的条件，变换就可以是任何复杂性。
因此，对于您的问题，答案不是，用于解决NP-完全问题的O（N ^ 2）算法并不意味着所有NP问题都可以在O（N ^ 2）时间内解决，它仅保证存在一个多项式时间算法来解决。
即O（N ^ 2）+ T（N），其中T（N）是转换问题实例的复杂度