非确定性多项式解优于确定性多项式解
非确定性多项式解总是不如确定性多项式解，这是真的吗？请给出适当的理由。
Non-Deterministic Polynomial solutions are always not desirable over Deterministic Polynomial solutions is it true? Please give an appropriate reasoning.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
每个确定性多项式解都可以转换为非确定性多项式解 [since P是 NP] 的子集
我们不知道是否相反是否正确[我们不知道P=NP还是P!=NP]，所以如果P!=NP，就会出现问题[all NP-Complete issues] ，我们有非确定性多项式解，但没有多项式解。
因此，由于我们可以将确定性多项式解转换为非确定性多项式解，但我们不知道是否可以做相反的事情 - 如果我们有确定性多项式解 - 我们实际上也有非确定性多项式解。
Every deterministic polynomial solution can be translated to a non-deterministic polynomial one [since P is a subset of NP]
We do not know if the oposite is true or not [we do not know if P=NP or P!=NP], so if P!=NP, there are problems [all NP-Complete problems] , which we have non deterministic polynomial solutions, but not polynomial solutions.
Thus, since we can convert deterministic polynomial solution to a non-deterministic polynomial solution, but we do not know if we can do the oposite - if we have a deterministic polynomial solution - we actuall have also the nondeterministic one.
作为对 amit 信息丰富的答案的补充，有时 - 对于实际输入 - NP 解决方案可能会更好。例如，考虑 T(n) = 2^n 的 NP 问题的指数算法。考虑一个问题，其最佳情况时间复杂度可证明为 T(n) = （1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00 0,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00 0,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00 0,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00 0,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,009)n^2。这是多项式，但我可能更愿意解决指数问题。
如果问题是，对于同一问题，您是否愿意使用指数或更差的解决方案或多项式解决方案，通常答案是这样的：这取决于您的输入大小。对于大多数合理大小的输入，具有较高渐近复杂度的算法可以更快；尽管在某个时刻使用较低复杂度的算法是有意义的，但在实践中（或在宇宙的生命周期中）可能永远无法达到这一点。
编辑：它还可以取决于输入的其他特征。例如，快速排序可以优于合并排序，尽管在最坏的情况下合并排序被证明比快速排序更好。如果您知道数据不太可能采用快速排序最坏情况的形式，那么快速排序可能值得尝试。
As a supplement to amit's informative answer, sometimes - for practical inputs - NP solutions can be better. For instance, consider an exponential algorithm for an NP problem which has T(n) = 2^n. Consider a problem whose best-case time complexity is provably T(n) = (1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,009)n^2. That's polynomial, but I'd probably rather solve the exponential problem.
If the question is whether, for the same problem, you'd rather use a an exponential-or-worse solution or a polynomial solution, generally the answer is this: it depends on your input size. Algorithms with higher asymptotic complexities can be faster for most inputs of reasonable size; although there will be a point where it makes sense to use the lower-complexity algorithm, that point may never be reached in practice (or in the lifetime of the universe).
EDIT: It can also depend upon other characteristics of the input. For instance, quicksort can outperform mergesort, although mergesort is provably better than quicksort in the worst case. If you know it's very unlikely for your data to be in a form such that it's the worst-case for quicksort, quicksort might be worth trying.