p\\u003dNp其實是一個地球上的未解難題,其中的p代表的是可以在一個多項式時間內解決的問題。
這問題過於複雜了,其實可以簡單的理解為,p問題就是給出多個值乘和加在一起,然後算出答案的問題,比如我問你1+1等於幾。
更複雜一點則是,在具有唯一值運算的機械上列舉一個多項式,多項式就是多個單項式的和,而單項式則可以是一個數字或者一個字母,也可以是數字和字母的乘積,也就說,1是單項式,a是單項式,1xa也是單項式,但不可以是1+a或者1-a,也不能是1除a。
而多項式的表達可以是1+a,這裡可以將1看成一個單項式,a看成一個單項式,那麼這就是一個多項式。
也可以是1xa+2xa,這裡可以將1xa看做一個單項式,2xa看向一個單項式,當然,多項式也可以是多個甚至無數個單項式,比如1xa+2xa+3xa+4xa……+100xa……
多項式時間則就是一個算法的運行時間複雜度為多項式,時間複雜度要簡單的解釋就是一個循環算法的運算時間,如果說它循環2次,運算的時間是原本1次的2倍,那麼這個算法的時間複雜度就可以,如果循環2次,運算時間卻是原本1次的3倍,那麼這個算法的時間複雜度就很高。
概念很抽象,因為這屬於信息學的知識。
而Np問題就又是一個更加抽象的問題了,它是在一個多項式時間中驗證或者猜測一個解的問題。
剛才說的p問題我們可以得到確定的答案,而Np問題本身就是不確定的,如果用簡單的語言來描述的話,那就比如你計算29+82等於多少,Np就是從1開始列舉出所有的答案來,一一確認和否認。
等於1?驗證結果是錯誤,等於2?驗證結果是錯誤……等於108,驗證結果是正確,那麼這才可以結束。
亦或者你可以直接猜,如果你厲害,你可以直接一次猜中是108,這猜並不是說運氣,而是通過其他方式確定猜出的答案在準確範圍內。
感覺一個是精確計算一個是窮舉法,似乎前者更好一些。
正是如此!
p\\u003dNp真正解決的問題是計算機運算邏輯的問題,1+1等於幾計算機當然可以辦到在短時間內完成,但是沒有人在網上詢問1+1等於幾,大部分問的是,宇宙有多大?人體有多少細胞或者原子?又比如一些運籌學問題,一些分子結構,基因結構的問題。
這樣的問題也是要依靠計算機的運算,那麼計算機如何用一般的計算來計算出宇宙多大,人體的細胞和原子有多少呢?它隻能非常複雜的進行的驗證和猜測,然而這種計算消耗的時間太多太多了。
p問題是一部分,Np問題是另外一部分,如果能將這兩者相等,就是將複雜Np問題簡化成p問題去解決,在同一套邏輯中兼容兩套問題的算法。
p\\u003dNp就是將一個用窮舉法計算出的數字回答是或者否回答的問題簡化成一項隻需要簡單的數學計算得出準確結果的問題。
p\\u003dNp對於計算機領域是巨大的進步,相當於數學領域的另類基本力的相互統一。
“所以,你可以更快更容易的解決更為複雜的問題了?”
這是El的一大步。