ひとくちに“手に負えない問題”といっても、計算可能性の理論と計算の複雑さの理論では、困難さのレベルが異なる。
計算可能性の理論では、「計算できるか？」 を考えているので、手に負えない＝計算不可能、つまり、それを解くプログラムがない場合を意味する。一方、計算の複雑さの理論では「どの程度の計算コストで計算できるか？」がテーマとなるので、手に負えない＝まともなコストでは計算不可能と解釈される。
本書では、この2種類の困難さの意味を明らかにし、いろいろな問題の難しさの解明をする。