NP 中間問題（NP-intermediate problems）

若你把 NP 想成一個國家，很容易只描繪出兩塊區域：容易的低地（P，我們能快速解出的問題）與險峻的高峰（NP 完全問題，NP 中最難的）。NP 中間問題就是被猜想存在於兩者之間的「山麓丘陵」——屬於 NP，但被相信「既不能」在多項式時間內解出、「也不是」NP 完全的問題。它們會是真正困難的，卻又沒難到能編碼整個 NP。它們的存在本身取決於那個著名的猜想，而領先的嫌疑犯都是極具實務重要性的問題。

精確地說，一個問題是 NP 中間，若它落在 NP 之內，卻既不在 P 中、也不是 NP 完全。這片中間地帶會不會是空的？Ladner 定理（1975）回答：「若」P 不等於 NP，那麼 NP 中間問題「必然」存在——NP 類無法塌縮成只有 P 加上 NP 完全問題；中間可被證明地存在一個無窮的難度階層。（Ladner 的證明是非構造性的，它建出一個人工填料的問題而非一個自然問題。）需要這個猜想，是因為若 P = NP，NP 中一切都會落在 P 裡，根本不會有任何中間地帶。所以「NP 中間問題存在」本質上等價於相信 P 不等於 NP。最著名的「自然」候選是整數分解（給定一個合數，找一個非平凡因數——它的決定性形式同時屬於 NP 與 co-NP，這使 NP 完全變得不太可能，然而沒有已知的多項式演算法）與圖同構（兩張圖在重新標記頂點後是否相同？——它數十年來既抵抗了多項式演算法、也抵抗了 NP 完全性證明，而 2015 年一個準多項式時間演算法把它逗人地推向 P，卻未抵達）。

為何要在意這條中間帶？一部分因為其中坐著一些最有用的未解問題，一部分因為它們特殊的地位對科技至關重要。質因數分解被推定的困難性是 RSA 密碼學的根基：若分解屬於 P，RSA 一夜崩潰；若它是 NP 完全，破解 RSA 就會和 NP 中一切一樣難——但它很可能的「中間」地位是一個微妙的甜蜜點，難到足以安全，卻又有結構到讓我們並非全然確定。誠實的說法是：NP 中間是個「被猜想」的類別。我們無法證明任何特定的自然問題是中間的，因為那麼做需要證明它不在 P 中（這會解決、或部分解決 P 對 NP）。所以這些最好被理解為：我們對一個自己強烈相信、卻尚未釘死的結構所做的最佳猜測——提醒著我們，關於計算困難性，仍有多少是真正未知的。