Reduction

#complexity-theory #reduction
Let $P_{1}, P_{2}$ be languages over alphabets $\sum_{1}, \sum_{2}$ respectively. We say that $P_{1}$ is (many-one logspace) reducible to $P_{2}$ if there is a function $f : \sum_{1}^{*} \mapsto \sum_{2}^{*}$ s.t.

$f$ can be computed by a deterministic TM using at most $\log n$ space on any work tape
for all $x \in \sum_{1}^{*}, x \in P_{1}$ if and only if $f (x) \in P_{2}$
We denote this as:

P_{1} \leq_{m}^{\log} P_{2}

This means any of the following:

$P_{2}$ is at least as hard as $P_{1}$
$P_{1}$ is no harder than $P_{2}$
if anyone shows an easy way of solving $P_{2}$ , we have an easy way of solving $P_{1}$

Complexity classes such as logspace, n-logspace, p-time and np-time are closed under many-one logspace reductions. Classes such as time(n), time( $n^{2}$ ), etc. are not closed under many-one logspace reductions.

Theorem

If $f_{1} : \sum_{1}^{*} \mapsto \sum_{2}^{*}$ and $f_{2} : \sum_{2}^{*} \mapsto \sum_{3}^{*}$ are both computable in logarithmic space, then so is $f_{2} \cdot f_{1} : \sum_{1}^{*} \mapsto \sum_{3}^{*}$

=> Logarithmic Space Reduction is a transitive notion

Let $P_{1}, P_{2}$ be problems over alphabets $\sum_{1}, \sum_{2}$ respectively. We say that $P_{1}$ is (many-one polytime) reducible to $P_{2}$ if there is a function $f : \sum_{1}^{*} \mapsto \sum_{2}^{*}$ s.t. for all $x \in \sum_{1}^{*}, x \in P_{1}$ if and only if $f (x) \in P_{2}$
We denote this as:

P_{1} \leq_{m}^{p} P_{2}

Polynomial Time Reduction is also a transitive notion

🔑 Definition

Let $C$ be a complexity class and $P$ a problem. We say that $P$ is $C$ -hard (under many-one logspace reducibility), if for all $P^{'} \in C$ , $P^{'} \leq_{m}^{\log} P$ .

Moreover, we say that $P$ is $C$ -complete if, $P \in C$ and $P$ is $C$ -hard