Karp還元
Polynomial-time Karp reducible
多項式時間多対一還元
$ \le_p
定義
$ L \subseteq 2^*が$ L' \subseteq 2^*にKarp還元可能である($ L \le_{p} L')とは, 多項式時間計算可能関数$ f : 2^* \to 2^*が存在して$ x \in L \iff f(x) \in L'が成り立つことである
$ L \le_p L' \iff \exists f : \text{poly-time computable}. \forall x. [x \in L \leftrightarrow f(x) \in L']
推移性$ L \le_p L' \Rightarrow L' \le_p L'' \Rightarrow L \le_p L''
Proof. 多項式時間計算可能な関数の合成は多項式時間計算可能 ❏