目录
tips:这里只是总结,不是教程哈。鉴于本人写字如画符,就不出视频教程了,如实在有需要,请在文章下方留言。当然,文章有任何问题,也请留言,谢谢!
这个系列用另一种形式,把习题放在最下面,看看好用不。
本系列文章最后一文会进行简要全部总结,以及思维导图放在最后一篇文章最下面,请自行获取。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
一类能够用确定的算法在多项式时间内求解的可判定问题(也称为多项式类型)
????????确定的算法:与之相反的算法叫随机化算法。
????????????????给定一个问题用这个算法去解决,得到的结果是唯一的。
????????????????用随机化算法,同样的输入每一次运行的结果可能不同。
????????可判定问题
一类能够用不确定的算法在多项式时间内求解的可判定问题
????????1、“猜”
????????2、猜出一个解来,在多项式时间以内,可以验证这个问题的正确性。
NP难问题满足NPC问题的性质2,不一定满足性质1;
NPC=NP交集NP难
P=NP意味着NP当中的所有问题都能有确定性算法,在多项式时间之内解决