NP与计算的难解性

本文同个人微信公众号(KeepYourAims)文章:NP与计算的难解性 对于一个算法,一般需要计算其时间复杂度和空间复杂度,以衡量它的效率。但是,有一些极其困难的问题,很难证明其不能用有效算法解决。因此,提出了一种归约方式,用于证明问题X至少像问题Y一样难。 参考书籍:《算法设计》《Algorithm Design》 1 多项式时间归约 1.1 归约的概念 在研究不同问题的难度时,希望表达“问题X至少像问题Y一样的难”,这就是归约。 1.2 多项式时间归约 在计算模型中,假设问题X可以在多项式时间内求解。如果有一个解决问题X的“黑盒子”,假设通过多项式次调用解问题X的黑盒子,可以解决问题Y,则说明问题X有足够的能力解决问题Y,称作“Y多项式时间可以归约到X”。 记作:Y \leq_p X,读作“Y多项式时间可以归约到X”或者“X至少像Y一样难。” 则,我们可以得到以下定理: 定理1.假设Y \leq_p X,如果可以在多项式时间内求解,则也可以在多项式时间内求解。 定理2.设Y

Read More