非確定性多項式難題

NP(Nondeterministic Polynomially，非確定性多項式)類問題是指一個複雜問題不能確定是否在多項式時間內找到答案，但是可以在多項式時間內驗證答案是否正確。NP類問題數量很大，如完全子圖問題、圖著色問題、旅行商(TSP)問題等。在P和NP問題中，P的難度最低，NP由於只對驗證答案的時間作了限定，從而有可能包含某些無法在多項式時間內找到答案的問題，即NP是比P更困難的問題。

基本介紹

• 中文名：非確定性多項式難題
• 外文名：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，那么依據計算複雜性的密碼技術就會沒有前途，因為答案很容易得到驗證的問題也同樣可以輕鬆求解，這將對計算機安全構成巨大威脅。因為目前的加密技術是將一個整數分解為幾個因數的乘積，正是因數分解過程煩瑣，才保證了信息的安全。

NPC(NP Complete，NP完全)問題

計算機科學家將NP問題中最困難的稱為NPC問題。NPC問題有一個令人驚訝的性質，即如果一個NPC問題存在多項式時間算法，那么所有NP問題都可以在多項式時間內求解，即P=NP成立。這是因為每一個NPC問題都可以在多項式時間內轉化成任何一個NP問題。只要任意一個NPC問題找到了一個多項式算法，那么所有NP問題都能用這個算法解決，也就解決了NP=P問題。但是給NPC找一個多項式算法太不可想像了，而且也從未成功，因此科學家認為，正是NPC問題的存在，使得人們相信P=NP。

NPC問題目前沒有多項式算法，只能用窮舉法逐個檢驗，最終得到答案。但是窮舉法的計算時間隨問題的複雜程度呈指數增長，很快問題就會變得不可計算了。

圍棋或象棋的博弈問題、西洋棋的n皇后問題、密碼學中的大素數分解問題等，都屬於NPC類問題。

解決NP問題的思路

解決NP問題的一種思路是減少指數的值，這可以節省大量的時間。另一種思路是降低對NP問題的最最佳化解，使用它的近似解。這方面的研究不僅包括如何得到近似解，也包括解的近似度和局限性，是NP問題的重要研究領域。