多項式時間多対一帰着（カープ帰着）

言語 $A, B \subseteq \Sigma^{*}$ について、関数 $f : \Sigma^{*} \to \Sigma^{*}$ が次の 2 条件を満たすとき、$f$ を $A$ から $B$ への多項式時間多対一帰着といい、$A \le_{\mathrm{p}} B$ と書きます。

1. $f$ は決定性チューリング機械により、入力 $x$ の長さの多項式時間で計算できる。
2. すべての $x \in \Sigma^{*}$ に対して、$x \in A \iff f(x) \in B$ が成り立つ。