如果一个NP在多项式时间内求解，可满足性在多项式时间内求解

基于下面的链接，我可以知道在多项式时间求解可满足性（NP Complete）意味着任何其他NP问题都可以在多项式时间内求解。但副 - 真的？另外，如果有任何其他NP-Complete问题的多项式是否意味着，所有其他NP-Complete都可以用多项式时间求解？如果一个NP在多项式时间内求解，可满足性在多项式时间内求解

What are the differences between NP, NP-Complete and NP-Hard?

来源

2015-04-28 user10000000

细说你的意思，反之亦然什么。 – orlp

所有NP完全问题是等价的，如果它们中的任何一个在多项式时间内都可解，则NP中的所有问题都可以用多项式时间求解。但是，这个问题真的是堆栈溢出的主题。更好的问问http://cs.stackexchange.com/ –

在NP完全的“完整的”意味着，如果一个问题，就是在NP完全，对于问题的解决方案给出了在NP与转换处理的多项式量解决任何问题。

通俗地说 - 如果你解决在多项式时间内一个单一的NP完全问题，你已经证明了NP = P。

来源

2015-04-28 04:32:01 orlp

是的，但是如果一个NP在多项式时间内求解，是否意味着在多项式时间内解决所有NP完全问题。 – user10000000

@ user10000000 No. – orlp

否。考虑例如电路评估问题（对P完成）。电路评估问题提出了“这个输入是否满足该布尔电路”的问题。电路评估问题显然在NP中，并包含一个多项式解决方案。但是，这并不意味着SAT电路具有多项式时间解决方案。如果考虑另一个NP完全问题，例如哈密顿路径问题，并且证明这个问题有多项式时间解，那么Satisfiability也有一个多时间解决方案。 –

如果一个NP在多项式时间内求解，可满足性在多项式时间内求解

回答

相关问题