机里的术语叫‘冒泡法’,其复杂度就是o(n^2),开发优越算法可以把复杂度降低,比如快速排序法的复杂度就是o(nlogn),显然要比n^2小,所以在计算机领域对于一个问题的难易看它的算法优越与否。”
“那么就不难理解了,人们研究每一个计算机的算法,目的就是把np类问题降到p类问题。可问题那么多,要找到猴年马月?那么,既然np问题是有一个共同点的,即,它们都可以在多项式时间内验证,会不会有另一个共同点?”
叶华自问自答:
“所以我们假设存在一种‘万能算法’,它能把所有的np问题降到p类问题,这就是「p=np?」问题。甚至都可以不用算出这个‘万能算法’是什么,只要能够证明或证伪,就可以拿百万大奖。”
旋即看向了学生们:“同时我们会发现,在np问题中有那么一小类问题,它们是明显要比p类问题难好多好多,在感觉上这些问题是最不可能成为p类问题的,而且这些问题也有一个共同点,一旦证明其中任何一个问题有一个优越算法能降到p类问题,那其它的问题也都能降到p类问题,换句话说只要证明了其中一个属于p,就是p=np。那么这一小类问题简称np-c,也就是