4 Reductions

A (decision) problem (a set) $A$ reduces to $B$ with reduction $f$ , in symbols $A ⩽_{f} B$ when $a \in A \Leftrightarrow f (a) \in B$ . We also have that $A ⩽_{f} B \Leftrightarrow \overset{―}{A} ⩽_{f} \overset{―}{B}$ because $x \in \overset{―}{A} \Leftrightarrow x \notin A \Leftrightarrow f (x) \notin B \Leftrightarrow f (x) \in \overset{―}{B}$ .

4.1 Reduction Relations

A relation of reductions ( $⩽_{F}$ ) can be defined on a class of functions $F$ as follows, note that $⩽_{F}$ is also a partial pre-order.

A ⩽_{F} B \Leftrightarrow \exists f \in F . A ⩽_{f} B

4.2 Properties

Let $D$ and $E$ two classes of problems such that $D \subseteq E$ , and $D \subseteq$ . A reduction relation̋_F classifies $D$ and $E \Leftrightarrow \forall A, B, C$ (problems):

1: Reflexivity	$A ⩽_{F} A$
2: Transitivity	$A ⩽_{F} B, B ⩽_{F} C \Rightarrow A ⩽_{F} C$
3: $D$ closed by reduction	$A ⩽_{F} B, B \in D \Rightarrow A \in D$
4: $E$ closed by reduction	$A ⩽_{F} B, B \in E \Rightarrow A \in E$

Equivalently:

1: Identity	$id \in F$
2: Closed by composition	$f, g \in F \Rightarrow f \circ g \in F$
3:	$f \in F, B \in D \Rightarrow {x ∣ f (x) \in B} \in D$
4:	$f \in F, B \in E \Rightarrow {x ∣ f (x) \in B} \in E$

4.3 Hard and Complete Problems

If $⩽_{F}$ classifies $D$ and $E$ , then $\forall$ problems $A, B, H$ .

`-`	$A ⩽_{F} B \land B ⩽_{F} A \Rightarrow A \equiv B$
`-`	$H$ is $⩽_{F}$ -hard for $E$ if $\forall A \in E . A ⩽_{F} H$
`-`	$H$ is $⩽_{F}$ -complete for $E$ if $\forall A \in E . A ⩽_{F} H \land H \in E$

Theorem

If $⩽_{F}$ classifies $D$ and $E$ , $D \subseteq E$ and $C$ is complete for $E$ then $C \in D \Leftrightarrow D = E$

Proof ▼

$(\Leftarrow)$ is obvious. $(\Rightarrow)$ : Let $C \in D$ and $A \in E$ . By completeness, $A ⩽_{F} C$ and $A \in D$ , then $E \subseteq D$ which implies $E = D$ □

Theorem

Completeness is "transitive" for reductions: If $A$ is complete for $E$ , $A ⩽_{F} B$ and $B \in E$ then $B$ is complete for $E$ .