algorithm - 关于 p、np 问题的理论

Question

我正在阅读 P 、 NP 和 NP 完全问题理论。这是文本片段。

The class NP includes all problems that have polynomial-time solutions, since obviously the solution provides a check. One would expect that since it is so much easier to check an answer than to come up with one from scratch, there would be problems in NP that do not have polynomial-time solutions. To date no such problem has been found, so it is entirely possible, though not considered likely by experts, that nondeterminism is not such an important improvement. The problem is that proving exponential lower bounds is an extremely difficult task. The information theory bound technique, which we used to show that sorting requires (n log n) comparisons, does not seem to be adequate for the task, because the decision trees are not nearly large enough.

我的问题是作者的意思是什么

1. 声明“到目前为止还没有发现这样的问题，所以这是完全有可能的，尽管 专家认为不太可能，非确定性并不是如此重要的改进。”?

2. 另一个问题，作者在最后一句话中所说的“因为决策树不够大”是什么意思。 ?

谢谢!

Answer 1

(1) 我认为作者的意思是没有找到NP问题，证明不在P中。当然也有NP问题没有多项式解已知，但这与知道不存在是不一样的。

如果事实上 P = NP(也就是说，如果实际上没有没有多项式解的 NP 问题)，那么在某种意义上，非确定性机器不是“比确定性机器更强大”，因为它们在多项式时间内解决了相同的问题。那么我们会说“不确定性并不是一个如此重要的改进”。

(2) n log n 证明的工作方式是排序函数有 n! 个可能的输出，其中任何一个都可能是正确的一个根据输入的顺序。每次比较都会在给定比较排序算法可以进入的所有可能状态的树中添加一条两条腿的分支。为了对任何输入进行排序，这个“决策树”必须有足够的分支来产生任何 n! 可能的输入重新排序，因此必须至少有 log( n!) 比较。因此，运行时的下限来自树的大小。

作者说，没有已知的 NP 问题，我们已经证明它们需要一棵如此大的树，以至于它暗示下界是超多项式。任何此类证明都将证明 P != NP。