多項式時間還元

ただの還元可能性ではなく、時間効率も考慮に入れた還元可能性

$ \alphaを$ \betaに多項式時間帰着可能である時$ \alpha\le^p_m \betaと表記する

$ \betaのほうが、$ \alphaより同等以上に難しい

このとき$ \alpha\le^p_m \betaと表記する

定義

$ \Sigma^\astの部分集合$ \alpha,\betaに対して

多項式時間計算可能関数$ fが存在して、任意の$ u\in\Sigma^\astに対して次が成り立つ

$ u\in\alpha\iff f(u)\in\beta

この$ fのことを多項式時間還元関数と言う

これが成り立つ時、$ \alphaが$ \betaに多項式時間還元可能と言う

$ \alpha\le^p_m\betaと表記する

定理

$ \alpha\le^p_m\betaかつ$ \beta\in Pならば、$ \alpha\in Pである

$ PはクラスPのことmrsekut.icon

証明

以下の2つのTMを用意して、結合して多項式時間TM $ Aを作る

$ \alpha\le^p_m\betaの多項式時間還元関数$ fを計算する多項式時間TM $ F

$ \beta\in Pを計算する多項式時間TM $ B

$ Aに$ uを入力すると、

$ f(u)が計算された後に、$ Bが動く

なので、$ f(u)\in \betaなら1、そうでなければ0を返す

結果的に$ Aは、$ \alphaを計算していることになるので成り立つ

参考