世界七大數學難題之一：P/NP問題

P/NP問題是在理論資訊學中計算複雜度理論領域裡至今沒有解決的問題，它也是克雷數學研究所七個千禧年大獎難題之一。P/NP問題中包含了複雜度類P與NP的關係。1971年史提芬·古克（Stephen A. Cook）和Leonid Levin相對獨立的提出了下面的問題，即是否兩個複雜度類P和NP是恆等的（P=NP?）。

複雜度類P即為所有可以由一個確定型圖靈機在多項式表達的時間內解決的問題；類NP由所有可以在多項式時間內驗證解是否正確的決定問題組成，或者等效的說，那些解可以在非確定型圖靈機上在多項式時間內找出的問題的集合。

很可能，計算理論最大的未解決問題就是關於這兩類的關係的：

有甲、乙、丙三個精靈,其中一個只說真話,另外一個只說假話.還有一個隨機地決定何時說真話,何時說假話.你可以向這三個精靈發問三條是非題,每條問題只可問一隻精靈,而你的任務是從他們的答案找出誰說真話,誰說假話,誰是隨機答話.這個難題困難的地方是這些精靈會以「Da」或「Ja」回答,但你並不知道它們的意思,只知道其中一個字代表「對」,另外一個字代表「錯」.你應該問那三條問題呢?