P-NP I}}題(P-NP problem)亦稱P=? NP問題，計算複雜性理論以及計算機理論中最重要的一個未解決問題。它問在多項式時間界下，確定型圖機接受的語言類是與非確定型圖靈機所接受的語言類NP是否是相同的.因為PcNP，所以，P-NP問題實際上是問這種包含關係是否是嚴格的，也即非確定型多項式時間算法是否確實比確定型多項式時間算法更有力.但是，至目前為止，只知道當某個問題SENP時，一定存在一個多項式p和常數。，使S的確定型複雜性界為為。·2a<.,>.即S為指數時間可計算的.
非確定型算法在多項式時間內有檢查指數個可能性的能力.這使人們覺得非確定型多項式時間算法確實比確定型多項式時間算法有力得多.事實上，儘管人們進行了持久不懈的努力，仍未找到NP中
許多著名問題(如巡迴售貨員問題、子圖同構等)的多項式時間算法.正是由於這些原因，現在人們普遍相信PNP，但始終沒有找到一個證明或否證.由於有許多重要的實際問題都已被證明是NP完全的.因此，研究P-NP問題有著十分重要的實際意義和理論價值.因為對P-NP問題的肯定或否定回答，可使對許多實際問題找到其“可行的”算法或者乾脆放棄這種努力。值得指出的是，英國數學家貝克(Baker , T.、吉爾(Gill , J.)和以色列學者索洛韋
非確定型算法在多項式時間內有檢查指數個可能性的能力.這使人們覺得非確定型多項式時間算法確實比確定型多項式時間算法有力得多.事實上，儘管人們進行了持久不懈的努力，仍未找到NP中
許多著名問題(如巡迴售貨員問題、子圖同構等)的多項式時間算法.正是由於這些原因，現在人們普遍相信PNP，但始終沒有找到一個證明或否證.由於有許多重要的實際問題都已被證明是NP完全的.因此，研究P-NP問題有著十分重要的實際意義和理論價值.因為對P-NP問題的肯定或否定回答，可使對許多實際問題找到其“可行的”算法或者乾脆放棄這種努力。值得指出的是，英國數學家貝克(Baker , T.、吉爾(Gill , J.)和以色列學者索洛韋
