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

\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のこと

証明

以下の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を計算していることになるので成り立つ

参考

『C言語による計算の理論』 p.161