Cook reduction

名詞

(computing theory) A Turing reduction that runs in polynomial time.

日本語の意味

多項式時間のチューリング縮約。計算理論において、ある問題を多項式時間内にチューリングマシンを用いて別の問題へ還元（縮約）する操作を指す。

その論文は、任意のSATのインスタンスを多項式時間で新しい制約問題のインスタンスに変換する多項式時間チューリング還元を提示している。

意味（1）

(computing theory) A Turing reduction that runs in polynomial time.

Cook reductions

（ plural ）