チューリング還元

ウィキペディア

チューリング還元

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 07:07 UTC 版)

チューリング還元（チューリングかんげん、英: Turing reduction）は、計算量理論における還元の一種である。アラン・チューリングの名がつけられた還元であり、問題 A が問題 B にチューリング還元されるとは、B が容易に解けると仮定したときに A が容易に解けることを意味する（Rogers 1967、Soare 1987）。より厳密に言えば、B を神託として備えた神託機械によってAが計算可能であることである。チューリング還元は決定問題にも関数問題にも適用できる。