還元 (計算複雑性理論)
自然数Nの部分集合 A と B があり、NからNへの関数の集合 F (関数合成において閉じている)があるとき、次の場合に F において A が B に還元可能である。
∃ f ∈ F . ∀ x ∈ N . x ∈ A ⇔ f ( x ) ∈ B {\displaystyle \exists f\in F{\mbox{ . }}\forall x\in \mathbb {N} {\mbox{ . }}x\in A\Leftrightarrow f(x)\in B}
これを次のように記述する。
A ≤ F B {\displaystyle A\leq _{F}B}
P(N) の部分集合 S があり、還元を ≤ で表すと、次の場合に ≤ において S が閉じている(closed)。
∀ s ∈ S . ∀ A ∈ P ( N ) . A ≤ s ⇔ A ∈ S {\displaystyle \forall s\in S{\mbox{ . }}\forall A\in P(\mathbb {N} ){\mbox{ . }}A\leq s\Leftrightarrow A\in S}
Nの部分集合 A は、次の場合に Sに対して困難(hard)である。
∀ s ∈ S . s ≤ A {\displaystyle \forall s\in S{\mbox{ . }}s\leq A}
AがSに対して困難で、かつAがSに含まれる場合に、Nの部分集合Aは S に対して完全(complete)である。