難解性／不易處理（intractability）
一個問題在輸入變大時讓電腦多花幾秒，和一個執行時間爆炸到連中等輸入都永遠搆不著的問題，兩者之間有著天壤之別。我們把後者稱為難解的：不是邏輯意義上的不可能（答案存在，給予無限時間演算法也能找到），而是實務上無望，因為所需時間隨輸入大小指數成長甚至更糟。那個嘗試 n 個項目全部 2^n 個子集的暴力搜尋，就是該記在心裡的圖像。
為什麼指數成長如此致命？因為每多一單位輸入是把工作「乘上」而非「加上」。假設一個 2^n 步演算法用一天處理 n = 50。那麼 n = 60 要 2^10 = 1024 天，將近三年；n = 70 約三千年；n = 80 比文明還長壽。更糟的是，更快的硬體幾乎幫不上忙：一台快一百萬倍的電腦只多讓你處理約 20 個元素，因為一百萬大約是 2^20。對比多項式方法：把輸入加倍只讓時間乘上一個固定倍數，而更快的機器則「乘上」你能處理的輸入。這種不對稱正是多項式對指數那條線成為可解與難解之分界的原因。
不過要在兩個方向上小心這個詞。第一，這裡的難解意指「就我們目前所能做到的而言，無法在多項式時間內解出」，而對許多著名問題（NP 完全問題），我們其實並沒有「不存在多項式演算法」的證明；我們只是強烈懷疑，因為 P 對 NP 仍是未決問題。第二，不可判定是更強且不同的判決：停機問題根本沒有任何演算法，不計代價皆然，而難解問題確實有演算法，只是慢得不切實際。難解意指慢到無法使用；不可判定意指根本不存在方法。
試圖用檢查 26 個字母表上每個長度為 n 的字串來破解密碼，意味著 26^n 次嘗試：26^6 約三億（快機器上幾秒），但 26^12 約 9 乘以 10^16（數十年）。每多一個字元就把工作乘上 26，這正是難解性的特徵；而對單一猜測做多項式時間的檢查則是瞬間完成。
指數成長讓每多一單位輸入就把工作乘上去，所以即使快速硬體也只多增加屈指可數的可行元素。
「難解」意指演算法存在但慢到不切實際（指數級）；它和「不可判定」（根本沒有演算法）不同。對 NP 完全問題而言，難解性是強烈懷疑但未經證明的（P 對 NP 未決）。