重大未解問題（the great open problems）
儘管這門學科已證明了如此多定理，它最著名的問題卻依然頑固地懸而未決——而且絕非因為數十年來眾多聰明人疏於嘗試。計算理論誠實的地圖上，有大片區域標著「我們強烈相信 X，卻無法證明它」。知道這些前沿在哪裡，不是教學的失敗；它是整個故事中最真實、最令人振奮的部分。
皇冠上的明珠是 P 對 NP：每個「解可被快速檢查」的問題，是否也是「解可被快速找到」的問題？幾乎所有人都相信 P 不等於 NP（檢查確實比求解容易），但無論朝哪個方向都沒有證明，而它還懸著百萬美元獎金。它遠非孤例。NL 對 P 問的是對數空間計算是否嚴格弱於多項式時間（相信是，未證）。BPP 對 P 問的是隨機性是否增加能力（透過去隨機化計畫，相信不——P = BPP——未證）。量子計算的真正威力未解：我們不確切知道 BQP 與古典類別的關係如何，只知道一般不相信量子電腦能攻克整個 NP。連 P 對 PSPACE——直覺上顯然多項式時間弱於多項式空間——也未被證明。
為何這些問題抵抗證明這麼久？答案的一部分本身就是定理：相對化、自然證明、代數化這類「障礙」定理顯示，一整批我們熟悉的證明技巧家族，被證明太弱而無法解決 P 對 NP——所以一個成功的證明必須用上我們尚未擁有的、真正嶄新的想法。我們確實知道的少數分離，來自一小組強大的工具：時間與空間階層定理證明了「嚴格更多的時間或空間」買得到「嚴格更多的能力」（所以 P 確實小於 EXPTIME，這是一個已證的分離），而對角線論證給了我們不可判定性。我們能證明的那一點點，與我們堅信的那一大堆，兩者之間的鴻溝，正是這個領域活生生的邊緣，而一位誠實的老師會把它清楚地說出來。
把「已知」與「相信」對照。時間階層定理「已證」：P 嚴格小於 EXPTIME——確實存在能在指數時間解、卻不能在多項式時間解的問題。儘管眾所相信，仍「未解」：P 是否嚴格小於 NP。我們能分離在資源尺度上相距甚遠的類別，但那些緊挨在一起的類別（P、NP、PSPACE）卻頑強地抗拒分離。
P 對 NP 及其同類是被相信、而非已證；只有相距甚遠的類別（P 對 EXPTIME）才被證明確實不同。
複雜度類別之間的大多數包含關係（P 對 NP、NL 對 P、BPP 對 P、P 對 PSPACE）是「猜想」而非已證。真正已知的分離只有少數——主要是階層定理，它給出 P 嚴格落在 EXPTIME 之內。要提防把這些未解問題說成定論的來源。