基本介紹
- 中文名：非確定性多項式難題
- 外文名：Nondeterministic Polynomially problem
- 簡稱：NP問題
- 舉例：完全子圖問題、旅行商問題等
- 相關概念：P問題，NPC問題等
基本介紹,P問題,NP問題,P=NP?問題,解決NP問題的思路,
基本介紹
在計算機領域，一般可以將問題分為可解問題和不可解問題。不可解問題也可以分為兩類：一類如停機問題，的確無解；另一類雖然有解，但時間複雜度很高。可解問題也分為多項式問題(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完全)問題
