Cook reduction（多項式時間のチューリング縮約。計）とは - 英語 - 英語

ログインすると広告が減り、学習に集中できます。

検索内容:

Cook reduction

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

日本語の意味

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

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

活用形複数形

plural of Cook reduction

原形: Cook reduction

日本語の意味

この単語は「Cook reduction」の複数形を表します。つまり、単数形「Cook reduction」に対して複数の要素を指す場合に用いられます。

Graduate students studying computational complexity often encounter Cook reductions when comparing the hardness of decision problems.

計算複雑性を学ぶ大学院生は、決定問題の難しさを比較する際にしばしばクックの還元に遭遇する。

Webで検索する