チューリング還元
第二の手法はチューリング還元を実装するプログラムが使用する計算資源を制限する手法である。これはPのような計算量に関する研究で重要である。集合 "A" が "B" に多項式時間チューリング還元可能であるとは、多項式時間で "A" を "B" にチューリング還元できることをいう。対数領域還元などの概念も同様である。