algorithm - 非确定性多项式解决方案优于确定性多项式解决方案

Question

与确定性多项式解决方案相比，非确定性多项式解决方案总是不可取的，这是真的吗？请给出适当的推理。

Answer 1

每个确定性多项式解决方案都可以转换为非确定性多项式解决方案[因为P是NP的子集]

我们不知道相反是否正确[我们不知道是 P=NP 还是 P!=NP]，所以如果 P!=NP，则存在问题 [所有NP-Complete questions]，我们有不确定性多项式解决方案，但不是多项式解决方案。

因此，由于我们可以将确定性多项式解决方案转换为非确定性多项式解决方案，但我们不知道是否可以相反 -如果我们有确定性多项式解决方案 - 我们实际上也有非确定性解决方案。

Answer 2

作为 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,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。这是多项式，但我可能更愿意解决指数问题。

如果问题是对于同一个问题，您是否更愿意使用指数或更差的解决方案或多项式解决方案，通常答案是这样的：这取决于您的输入大小。对于大多数合理大小的输入，具有更高渐近复杂度的算法可以更快；尽管在某个时刻使用低复杂度算法是有意义的，但在实践中（或在宇宙的生命周期中）可能永远无法达到这一点。

编辑：它也可以取决于输入的其他特征。例如，快速排序可以胜过归并排序，尽管在最坏的情况下归并排序可以证明比快速排序更好。如果您知道您的数据不太可能采用快速排序的最坏情况，那么快速排序可能值得一试。