4 Reductions
A (decision) problem (a set) \(A\) reduces to \(B\) with reduction \(f\), in symbols \(A \leqslant _{f} B\) when \(a \in A \Leftrightarrow f(a) \in B\). We also have that \(A \leqslant _{f} B \Leftrightarrow \overline{A} \leqslant _{f} \overline{B}\) because \(x \in \overline{A} \Leftrightarrow x \notin A \Leftrightarrow f(x) \notin B \Leftrightarrow f(x) \in \overline{B}\).
4.1 Reduction Relations
A relation of reductions (\(\leqslant _{F}\)) can be defined on a class of functions \(F\) as follows, note that \(\leqslant _{F}\) is also a partial pre-order.
4.2 Properties
Let \(\mathcal{D}\) and \(\mathcal{E}\) two classes of problems such that \(\mathcal{D}\subseteq \mathcal{E}\), and \(\mathcal{D}\subseteq \). A reduction relatioǹ‹_F\(\) classifies \(\mathcal{D}\) and \(\mathcal{E}\Leftrightarrow \forall A,B,C\) (problems):
|
1: Reflexivity |
\(A \leqslant _{F} A\) |
|
2: Transitivity |
\(A \leqslant _{F} B, B \leqslant _{F} C \Rightarrow A \leqslant _{F} C\) |
|
3: \(\mathcal{D}\) closed by reduction |
\(A \leqslant _{F} B, B \in \mathcal{D}\Rightarrow A \in \mathcal{D}\) |
|
4: \(\mathcal{E}\) closed by reduction |
\(A \leqslant _{F} B, B \in \mathcal{E}\Rightarrow A \in \mathcal{E}\) |
Equivalently:
|
1: Identity |
\(\text{id} \in F\) |
|
2: Closed by composition |
\(f,g \in F \Rightarrow f \circ g \in F\) |
|
3: |
\(f \in F, B \in \mathcal{D}\Rightarrow \{ x \mid f(x) \in B \} \in \mathcal{D}\) |
|
4: |
\(f \in F, B \in \mathcal{E}\Rightarrow \{ x \mid f(x) \in B \} \in \mathcal{E}\) |
4.3 Hard and Complete Problems
If \(\leqslant _{F}\) classifies \(\mathcal{D}\) and \(\mathcal{E}\), then \(\forall \) problems \(A,B,H\).
|
|
\(A \leqslant _{F} B \wedge B \leqslant _{F} A \Rightarrow A \equiv B\) |
|
|
\(H\) is \(\leqslant _{F}\)-hard for \(\mathcal{E}\) if \(\forall A \in \mathcal{E}. \ A \leqslant _{F} H\) |
|
|
\(H\) is \(\leqslant _{F}\)-complete for \(\mathcal{E}\) if \(\forall A \in \mathcal{E}. \ A \leqslant _{F} H \wedge H \in \mathcal{E}\) |
If \(\leqslant _{F}\) classifies \(\mathcal{D}\) and \(\mathcal{E}\), \(\mathcal{D}\subseteq \mathcal{E}\) and \(C\) is complete for \(\mathcal{E}\) then \(C \in \mathcal{D}\Leftrightarrow \mathcal{D}= \mathcal{E}\)
\((\Leftarrow )\) is obvious. \((\Rightarrow )\): Let \(C \in D\) and \(A \in \mathcal{E}\). By completeness, \(A \leqslant _{F} C\) and \(A \in \mathcal{D}\), then \(\mathcal{E}\subseteq \mathcal{D}\) which implies \(\mathcal{E}= \mathcal{D}\)
Completeness is "transitive" for reductions: If \(A\) is complete for \(\mathcal{E}\), \(A \leqslant _{F} B\) and \(B \in \mathcal{E}\) then \(B\) is complete for \(\mathcal{E}\).