“千年難題”之一：Ｐ（多項(xiàng)式算法）問(wèn)題對(duì)ＮＰ（非多項(xiàng)式算法）問(wèn)題

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

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