“千年難題”之一：Ｐ（多項式算法）問題對ＮＰ（非多項式算法）問題

　　在一個周六的晚上，你參加了一個盛大的晚會。由于感到局促不安，你想知道這一大廳中是否有你已經(jīng)認識的人。你的主人向你提議說，你一定認識那位正在甜點盤附近角落的女士羅絲。不費一秒鐘，你就能向那里掃視，并且發(fā)現(xiàn)你的主人是正確的。然而，如果沒有這樣的暗示，你就必須環(huán)顧整個大廳，一個個地審視每一個人，看是否有你認識的人。生成問題的一個解通常比驗證一個給定的解時間花費要多得多。

　　這是這種一般現(xiàn)象的一個例子。與此類似的是，如果某人告訴你，數(shù)１３，７１７，４２１可以寫成兩個較小的數(shù)的乘積，你可能不知道是否應(yīng)該相信他，但是如果他告訴你它可以因式分解為３６０７乘上３８０３，那么你就可以用一個袖珍計算器容易驗證這是對的。不管我們編寫程序是否靈巧，判定一個答案是可以很快利用內(nèi)部知識來驗證，還是沒有這樣的提示而需要花費大量時間來求解，被看作邏輯和計算機科學(xué)中最突出的問題之一。它是斯蒂文·考克于１９７１年陳述的。