P/NP問題是在理論資訊學中計算複雜度理論領域裡至今沒有解決的問題，它也是克雷數學
研究所七個千禧年大獎難題之一。P/NP問題中包含了複雜度類P與NP的關係。1971年史提
芬極j克（Stephen A. Cook）和Leonid Levin（英語：Leonid Levin）相對獨立地提出了
下面的問題，即是否兩個複雜度類P和NP是恆等的（P=NP?）。
複雜度類P即為所有可以由一個確定型圖靈機在多項式表達的時間內解決的問題；類NP由
所有可以在多項式時間內驗證解是否正確的決定問題組成，或者等效的說，那些解可以在
非確定型圖靈機上在多項式時間內找出的問題的集合。很可能，計算理論最大的未解決問
題就是關於這兩類的關係的：
P和NP相等
在2002年對於100研究者的調查，61人相信答案是否定的，9個相信答案是肯定的，22個不
確定，而8個相信該問題可能和現在所接受的公理獨立，所以不可能證明或證否。[1]Ö於正確的解答，有一個1,000,000美元的獎勵。
NP-完全問題（或者叫NPC）的集合在這個討論中有重大作用，它們可以大致的被描述為那
些在NP中最不像在P中的（確切定義細節請參看NP-完全理論）。電腦科學家現在相信P,嘅
P，和NPC類之間的關係如圖中所示，其中P和NPC類不交。
假設PNP的複雜度類的圖解。如Pꀽ嘅P則三個類相同。
簡單來說，Pꀽ嘅P問題問道：如果是／不是問題的正面答案可以很快驗證，其答案是否也
可以很快計算？這裡有一個給你找點這個問題的感覺的例子。給定一個大數Y，我們可以
問Y是否是複合數。例如，我們可能問53308290611是否有非平凡的因數。答案是肯定的，
雖然手工找出一個因數很麻煩。從另一個方面講，如果有人聲稱答案是"對，因為224737
可以整除53308290611"，則我們可以很快用一個除法來驗證。驗證一個數是除數比找出一
個明顯除數來簡單得多。用於驗證一個正面答案所需的資訊也稱為證明。所以我們的結論
是，給定正確的證明，問題的正面答案可以很快地（也就是，在多項式時間內）驗證，而
這就是這個問題屬於NP的原因。雖然這個特定的問題，最近被證明為也在P類中（參看下
面的關於"質數在P中"的參考），這一點也不明顯，而且有很多類似的問題相信不屬於類P
。
像上面這樣，把問題限制到「是／不是」問題並沒有改變原問題（即沒有降低難度）；即
使我們允許更複雜的答案，最後的問題（是否FP=啫NP）是等價的。
https://zh.m.wikipedia.org/zh-tw/P/NP问题
明明是中文卻看不懂 看來我沒有天分
能編輯這個中文頁面也是強者
有八卦嗎？