这样做的好处有两点。
一是找到自己思路的死角,解决隐藏的问题。
二是,错题集可以发挥威力了。
“按照一般的解法,完全多项式非确定性问题的答案,可以用穷举法来得到,只要一个个检验下去,最终便能得到结果。”
“但是,算法的问题就会凸显出来,算法的复杂程度是指数关系,这个算法的时间,随问题的复杂程度成指数的增长,很快就变得不可计算了。”
“到这里的话,就能推到NP完全问题身上了,只是……”
陈舟边梳理,边把问题转移到了NP完全问题上。
这也是最初提出这个问题时,学术界的人所走的路。
因为所有的完全多项式非确定性问题,都可以转换为一类叫做满足性问题的逻辑运算问题。
那么,如果这类问题的所有可能答案,都可以在多项式时间内计算,是不是这类问题存在一个确定性算法,可以在多项式时间内直接算出或是搜寻出正确的答案呢?
这也就是著名的NP完全问题的猜想。
现在学术界关于解决这个猜想的思路,也提出了两种可能。
一种是找到一个可能存在的算法,只要针对某个特定NP完全