-
P類問題
鎖定
目錄
P類問題P=NP
複雜度類P即為所有可以由一個確定型圖靈機在多項式表達的時間內解決的問題;類NP由所有可以在多項式時間內驗證它的解是否正確的決定問題組成,或者等效的説,那些可以在非確定型圖靈機上在多項式時間內找出解的問題的集合。很可能,計算理論最大的未解決問題就是關於這兩類的關係的:P和NP相等
[2]
。
P類問題P類和NP類問題
P類問題NP完全問題
NP-完全問題( Np-complete problem)是計算複雜性理論中最重要的一部分內容。在計算科學和計算機科學理論中,NP完全問題也有着十分重要的地位。因為其重要性,NP-完全問題理論已發展成為一個獨立的學科分支
[3]
。
粗略地説,NP完全問題是這樣的一大類問題:如果對該類中的某一個問題設計出多項式時間複雜性的電子計算機算法,那麼該類中的每一個問題也都存在多項式時間複雜性的電子計算機算法;反之,如果證明了該類中的某一個問題不存在多項式時間的電子計算機算法,那麼該類中的所有問題也不可能存在多項式時間複雜性的電子計算機算法
[3]
。
雖然NP完全問題的研究目標是為了確定一大類問題是否存在多項式時間複雜性的電子計算機算法,但在研究方法和手段上,還是藉助圖靈機這種計算模型。具體地説,確定的圖靈機和不確定的圖靈機在計算複雜性上的差異是NP-完全問題研究的出發點
[3]
。
P類問題P類問題的實例
矩陣乘法是一個P類問題。對兩個n階方陣的乘積,即使採用求內積分別求積矩陣中各個元素的方法,其時間界也只有
(n3),如果採用矩陣乘法的 Stressen算法或凝聚算法,,則可以使時間界進一步降低
[3]
。
查找問題是一個P類問題。在n個有序的數集合{a1,a2,…,an}中查找一個數b,若採用二分查找算法,其時間複雜度僅為
(log2n),這是比線性時間界還要低得多的一個複雜度,當然也是多項式時間界的
[3]
。
P類問題計算機科學家為什麼認為P≠NP?
大多數理論計算機科學家相信P≠NP,是因為他們確實找到一類問題NPC,這類問題有令人非常驚奇的性質,即如果NPC中任何一個問題能夠在多項式時間內找到最優解,則NP中的每個問題都能在多項式時間內找到最優解,即P=NP。儘管研究了大半個世紀,但是還沒有找到任何一個NPC問題的多項式時間算法。在給出NPC的定義之前,我們先介紹問題約簡的概念
[4]
。
直觀地,如果一個問題Q的任一實例能夠容易地轉化為另一個問題Q'的一個實例,則説問題Q能夠約簡到問題Q,這樣問題Q'實例的解就可以看作問題Q相應實例的解。例如解線性方程的問題可以約簡到解二次方程。例如線性方程的一個實例ax+b=0可以轉化為二次方程的一個實例0x2+ax+b=0,這樣實例0x2+ax+b=0的解就是實例ax+b=0的解。這樣問題Q能夠約簡到問題Q,從某種意義上説,Q不會比Q'更難解
[4]
。