NP完全学习小结1

NP完全学习小结1

连续学习这个章节已经大概有两周了,学习进度慢的原因有两个:

  1. 这部分的内容的确很难
  2. 最近节假日比较多,而且个人还在考虑职业规划的问题,所以有点分心。

无论如何,现在先总结一下吧。注:本人还是不太会用严格的语言来描述问题。

P类问题是指一类可以在多项式时间内解决的问题。

NP类问题是指一类可以再多项式时间验证的问题。

NP完全问题是指可以在多项式时间内验证,但是难度又是跟别的NP问题一样难的问题。这里的难(hard)指的是,一旦确定它是一个NP完全问题,那么任何NP问题都可以用这个问题规约。

规约是指可以用这个问题的解在多项式时间解决另一个问题。

NP完全问题之所以有这么大的魅力是因为,一旦在多项式时间解决了一个NP完全问题,那么就证明了P=NP。现在这个问题还没有答案。

接下来还学习了一些NP完全问题,如下图。目前的困扰是不熟悉这些问题,我的学习方式比较倾向于通过例子来理解,而这节的介绍中例子比较少,所以不太理解其中的例子,郁闷中。介绍这些NP完全问题,是因为如果面对一个问题,可以通过其中的已知的NP完全问题规约,那么就说明这个问题是NP完全问题。

Leave a Reply

Your email address will not be published. Required fields are marked *