ven*_*rty 2 theory algorithm complexity-theory
我正在阅读P,NP和NP-Complete问题理论.这是文本片段.
NP类包括具有多项式时间解的所有问题,因为显然该解决方案提供了检查.人们会期望,因为检查答案比从头开始提出答案要容易得多,所以NP中存在没有多项式时间解决方案的问题.到目前为止还没有发现这样的问题,所以尽管专业人士认为不可能,但非确定性并非如此重要.问题是证明指数下限是一项极其困难的任务.信息理论约束技术,我们用来表明排序需要(n log n)比较,似乎不适合任务,因为决策树不够大.
我的问题是作者的意思
声明"到目前为止还没有发现这样的问题,所以尽管专家们认为不可能,但非确定性并非如此重要." ？
另一个问题是作者在最后一句话中的意思是"因为决策树不够大." ？
谢谢!
(1)我认为作者意味着没有找到NP问题,事实证明它不在P中.当然,在NP中存在没有多项式解已知的问题,但这与知道它不同.都不存在.
事实上P = NP(也就是说,如果实际上没有没有多项式解决方案的NP问题),那么在某种意义上,非确定性机器并不比确定性机器"更强大",因为它们解决了相同问题.多项式时间的问题.然后我们会说"不确定性不是一个重要的改进".
(2)n log n证明的工作方式是,n!排序函数可能有输出,根据输入的顺序,任何一个输出都可能是正确的.每个比较都会在树中添加一个两条腿的分支.给定比较排序算法可以进入的所有可能状态.为了对任何输入进行排序,该"决策树"必须具有足够的分支以产生输入的任何n!可能的重新排序,因此必须至少log(n!)进行比较.因此,运行时的下限来自树的大小.
作者说,没有已知的NP问题,我们已经证明它们需要一个如此大的树,以至于它意味着一个超多项式的下界.任何这样的证据都证明了P != NP.