-
非確定性多項式難題
鎖定
- 中文名
- 非確定性多項式難題
- 外文名
- Nondeterministic Polynomially problem
- 簡 稱
- NP問題
- 舉 例
- 完全子圖問題、旅行商問題等
- 相關概念
- P問題,NPC問題等
非確定性多項式難題基本介紹
在計算機領域,一般可以將問題分為可解問題和不可解問題。不可解問題也可以分為兩類:一類如停機問題,的確無解;另一類雖然有解,但時間複雜度很高。可解問題也分為多項式問題(Polynomial Problem,P問題)和非確定性多項式問題(NondeterministicPolynomial Problem,NP問題)。
非確定性多項式難題P問題
P問題是一個判定問題類,這些問題可以用一個確定性算法在多項式時間內判定或解出。如果一個判定性問題的複雜度是該問題的一個實例的規模n的多項式函數,則我們説這種可以在多項式時間內解決的判定性問題屬於P類問題。P類問題就是所有複雜度為多項式時間的問題的集合。
確定一個問題是否是多項式問題,在計算機科學中非常重要。已經證明,多項式問題是可解問題,因為除了P問題之外的問題,其時間複雜度都很高,即求解需要大量時間。
理論上有解但其時間複雜度巨大的問題,科學家將其稱為難解型問題。對計算機來説,這類問題是不可解的。因此,P問題成了區別問題是否可以被計算機求解的一個重要標誌。
非確定性多項式難題NP問題
NP問題是指可以在多項式時間內被非確定機解決的問題。通常它們的時間複雜度都是指數變量,如
等。
這裏有一個著名的問題一千禧難題之首。是説P問題是否等於NP問題,也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解。這表明用NP問題尋找多項式時間表示的算法很困難,或許最後的結論是NP問題根本就不是P問題。
非確定性多項式難題P=NP?問題
目前已經證明所有P問題都是NP問題,那麼反之P—NP嗎?這就是所謂的“NP問題”。目前P與NP是否等價是一個既沒有證實也沒有證偽的問題。但是大部分科學家猜想:找一個問題的解很困難,但驗證一個解很容易(證比解易),用公式表示就是P≠NP。問題較難求解(P)但容易驗證(NP),這與我們的日常生活經驗是相符的。
【例1】對方程
求解很難,但是驗證
很容易。
假設證明了P=NP,那麼依據計算複雜性的密碼技術就會沒有前途,因為答案很容易得到驗證的問題也同樣可以輕鬆求解,這將對計算機安全構成巨大威脅。因為目前的加密技術是將一個整數分解為幾個因數的乘積,正是因數分解過程煩瑣,才保證了信息的安全
[1]
。
NPC(NP Complete,NP完全)問題
計算機科學家將NP問題中最困難的稱為NPC問題。NPC問題有一個令人驚訝的性質,即如果一個NPC問題存在多項式時間算法,那麼所有NP問題都可以在多項式時間內求解,即P=NP成立。這是因為每一個NPC問題都可以在多項式時間內轉化成任何一個NP問題。只要任意一個NPC問題找到了一個多項式算法,那麼所有NP問題都能用這個算法解決,也就解決了NP=P問題。但是給NPC找一個多項式算法太不可想象了,而且也從未成功,因此科學家認為,正是NPC問題的存在,使得人們相信P=NP。
圍棋或象棋的博弈問題、國際象棋的n皇后問題、密碼學中的大素數分解問題等,都屬於NPC類問題。