例如，考慮完美匹配、點集覆蓋和圖形異構的問題。這三個問題都有圖論的後盾，問題描述如下:
完美匹配問題:給定圖G=(V，E)，求邊的子集f？e，使得對於任意v∈V，存在唯壹的e∈F，V∈e；點集覆蓋問題:給定圖G=(V，E)和自然數K，求點U的子集？v，使得對於任意e∈E，有v∈U，v∈e，且| U |≤k；圖異構問題:給定圖G=(V，E)，H=(U，F)，|G|=|H|。當我們說G和H同構時，我們指的是什麽？T:V→U，對任意s，t∈V，E(s，t)=F(T(s)，T(t))(這裏我們把邊集E看成V×V→{0，1}的映射)。圖的不同結構是問對G和h是否不存在這樣的映射，關於這三個問題，它們在復雜性理論中的現狀如下:
完美匹配問題:在P. Edmond算法中可以使用得到運行時間的算法；點集覆蓋問題:在n P中，但不知道是否在p中，實際上這是壹個NP完全問題，給出它的多項式算法就意味著證明NP = P，它在NP中是因為給定了壹個點的子集，u？v，我們可以在多項式時間內驗證這是否是滿足|U|≤k的點集覆蓋:U的大小很好驗證。然後，對於每個邊E，遍歷U中的每個元素V，檢查是否有V ∈ E..運行時間最多是o(ve)；圖異構問題:在AM，但不知道是否在NP。之所以難，是壹個直觀的想法:給定兩個圖G和H，這個問題的“證據”壹開始很難定義——與點集覆蓋問題不同，壹個解是壹個點集，點集大小≤k≤|V|是壹個多項式大小。這裏證據最直接的定義是指我們必須遍歷所有映射T:V→U，驗證所有映射是否滿足同構的定義。這樣的證據是指數級的。這樣我們就有了三個問題:在P中，在n P中而不知道是否在P中，在AM中而不知道是否在NP中。因為可以在多項式時間內判斷X是否在L中，包含了X本身就是它在L中的證據的意思，所以P？NP .這種包含關系嚴格嗎？或者說，有沒有壹種語言L∈NP使得L？p？這就是著名的NP和p之間的關系。自從這個問題在1970年代被正式提出以來，NP-完備理論在實踐中賦予了它重要性，證明復雜性理論在純數學理論中賦予了它重要性，PCP理論和NP-完備理論在算法理論中賦予了它重要性。這些理論要麽從根本上依賴於關於NP和P之間關系的壹些假設，要麽是通過試圖理解NP和P之間的關系而發展起來的，這使得它成為理論計算機科學甚至數學的中心問題之壹。2000年，格洛裏亞數學研究所提出了新世紀數學的七個中心問題，NP與P的關系就是其中之壹。
關於名詞短語和名詞短語關系的最早理論是名詞短語完全理論。在下壹節中，我們將簡要地理解NP完全理論。主項目:NP完成
從以上歸約知識中我們知道，算法問題之間的相對難度可以根據歸約來定義。即對於問題A和問題B，我們認為A比B簡單，標為A≤B，即有壹個算法M用問題B的解來解問題A，M是多項式時間。那麽，在壹個復雜的類中，有可能出現“最難的問題”嗎？具體到NP，也就是說有問題A∈NP使其正確嗎？B∈NP，那麽B≤A呢？對於這樣的問題，我們稱之為NP完全。
乍壹看，這個問題不好把握。因為它需要為NP中的所有語言L找到壹個從L到A的歸約算法。然而，由Stephen Cook和Leonid Levin在1970年發現的Cook-Levin定理證明了布爾公式的可滿足性問題(SAT問題)是NP完全的。綜上，他們證明了在非確定性圖靈機上用布爾表達式對NP中任意語言的運行歷史進行編碼有壹個壹般過程，使得布爾表達式滿足當且僅當運行歷史是針對給定輸入的。這樣，我們就有了第壹個被證明是NP完全的問題。
在庫克證明SAT問題是NP完全的後不久，理查德·卡普證明了圖論和組合數學中的265，438+0個常見問題是NP完全的。這使得NP完全問題在實踐中變得非常重要。現在，實踐中遇到的上千個算法問題都被證明是NP完全的(見NP完全問題列表)。尤其是許多問題的最優算法，比如旅行商問題，會帶來巨大的經濟效益(旅行商問題的最優解可以給出最優的電路布線方案，而SAT的最優算法會促進程序驗證等問題的進度)。從NP完全的定義我們知道，這些問題中任何壹個問題的多項式算法都會給出所有的NP完全問題，包括所有的NP完全問題。然而，盡管實際問題中存在許多NP完全問題，而且許多問題在不同領域都具有相當的重要性，但仍然沒有針對NP完全問題的多項式算法，這也是壹些理論計算機科學家認為NP ≠ P的原因之壹。
對於NP與P的關系，NP-完全理論給出了以下提示:如果要證明NP=P，壹個可能的方向是給出NP-完全問題的多項式算法；如果要證明NP≠P，那麽壹個必然的結果就是NP完全問題沒有多項式算法。主要項目:電路復雜性
在1990之前，電路復雜性理論被許多研究者認為是解決NP與p關系問題的可能途徑之壹，電路復雜性的研究對象是非均勻計算模型電路，考慮的是計算壹個布爾函數所需的最小電路深度和尺寸。其中能用多項式大小的電路族計算的布爾函數記為P/poly。可以證明P包含在P/poly中，Karp-Lipton定理表明如果P/poly在n P中，多項式的層次會塌縮到第二級，這是不太可能的結果。這兩個結果結合起來說明P/poly可以作為分離NP和P的中間工具，具體方式是證明任意NP完全問題的電路規模的下界。直觀來說，電路的復雜性也繞過了NP和P問題的第壹個難點:相對化證明。
在1980年代，電路復雜性方法取得了壹系列成功，包括AC中奇偶函數的下界是指數的，單調電路中團問題的下界是指數的。但在1994中Razborov和Rudich的著名論文《自然證明》中指出，在單向函數存在的情況下，NP和P是不可能分離的。這個結果讓很多專家不看好證明分離NP和p的電路下界的前景，計算復雜性理論的基本課題之壹就是算法所需資源的下界。隨著算法理論的發展，如隨機算法和近似算法的發現，計算復雜性理論也展開了對隨機算法的去隨機化和近似困難性的研究。有趣的是，這些理論與NP和P的關系以及電路的復雜程度密切相關。下面是理論計算機科學基於NP和P的關系發展起來的壹些理論，簡單介紹壹下它們的研究進展:
交互證明系統理論；去隨機化理論:包括偽隨機發生器和提取器的構造等。不可逼近性:基於PCP定理、NP≠P和更強的唯壹對策猜想，可以證明對於某些問題不存在具有壹定逼近比的逼近算法；