关于 p、np 问题的理论
我正在阅读 P 、 NP 和 NP 完全问题理论。这是文本片段。
NP 类包括所有具有多项式时间的问题 解决方案，因为显然该解决方案提供了检查。一个会 期待这一点，因为检查答案比检查答案容易得多 如果从头开始想出一个，那么 NP 中就会出现这样的问题 没有多项式时间解。 到目前为止还没有出现这样的问题 发现，所以这是完全可能的，尽管不太可能 专家认为，非决定论并不是一个重要的改进。这 问题是证明指数下界是一个极其困难的事情 艰巨的任务。我们使用的信息论绑定技术 表明排序需要 (n log n) 次比较，似乎并不 足以完成任务，因为决策树并不接近 足够大。
是什么意思
- 我的问题是作者所说的
声明“到目前为止还没有发现这样的问题，所以这是完全有可能的” 专家们认为不太可能，非决定论并不是一个如此重要的改进。”？
另一个问题，作者在最后一句话中所说的“因为决策树还不够大”是什么意思。？
？
I am reading about P , NP and NP-Complete problems theory. Here is text snippet.
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.
My question is what does author mean by
by statement "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." ?Another question what does author mean by in last statement by "because the decision trees are not nearly large enough." ?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
(1) 我认为作者的意思是没有发现NP问题，因此已证明它不在P中。NP中当然存在不知道多项式解的问题，但是这与知道不存在不一样。
如果实际上
P = NP（也就是说，如果实际上不存在没有多项式解的NP问题），那么在某种意义上，非确定性机器并不“更强大”比确定性机器更好，因为它们在多项式时间内解决相同的问题。然后我们会说“非决定论并不是一个如此重要的改进”。(2)
n log n证明的工作方式是，排序函数有n!个可能的输出，其中任何一个都可能是正确的输出，根据输入的顺序是什么。每次比较都会向给定比较排序算法可以进入的所有可能状态的树添加一个两条腿的分支。为了对任何输入进行排序，这个“决策树”必须有足够的分支来产生任何n!可能的输入重新排序，因此必须至少有log( n!)比较。因此，运行时间的下限来自树的大小。作者的意思是，我们已经证明没有任何已知的 NP 问题需要一棵如此大的树，以至于它意味着一个超多项式的下界。任何这样的证明都会证明
P != NP。(1) I think the author means that no NP problem has been found, for which it is proven that it is not in P. Certainly there are problems in NP for which no polynomial solution is known, but that's not the same as knowing that none exists.
If in fact
P = NP(that is to say, if in fact there are no NP problems that don't have a polynomial solution), then in some sense a nondeterministic machine is no "more powerful" than a deterministic machine, since they solve the same problems in polynomial time. Then we'd say "nondeterminism is not such an important improvement".(2) The way that the
n log nproof works is that there aren!possible outputs from a sorting function, any one of which might be the correct one according to what order the input was in. Each comparison adds a two-legged branch to the tree of all possible states that a given comparison sort algorithm can get into. In order to sort any input, this "decision tree" must have enough branches to produce any of then!possible re-orderings of the input, and hence there must be at leastlog(n!)comparisons. So, the lower bound on runtime comes from the size of the tree.The author is saying that there are no known NP problems for which we've proved they require a tree so large that it implies a lower bound that is super-polynomial. Any such proof would prove
P != NP.作者给出了某人可能想出一个非指数时间的 NP 完全问题解决方案的可能性。
第二部分有点含糊，他似乎认为我们都同意的搜索树的下界是 O(n log n) ，这是通过信息论得出的，如果我们使用大型决策树，这可以进一步减少下界界限。这真的很模糊。
顺便说一句，在所有 NP 相关流行语解释的介绍中，我发现这超级令人困惑，这是来自哪本书/章节？
Micheal Sipser 的《计算理论》是一本不错的教材，或者听一下 Shai Simonson 的讲座。
The Author gives the possibility of someone may come up with a solution to NP-Complete problems that is not exponential time.
The second part is little vague, he seems so that the lower bound of search tree which we all agree to be O(n log n) is by information theory and if we use large decision trees, which can furture reduce the lower bounds. This is really vague.
BTW, of all the introductions to NP related buzzword explainations, I find this super confusing, which book/ chapter is this from?
A good text is Micheal Sipser's Theory of Computation or listen to Shai Simonson's lectures.