Notes - Computational Complexity HT25, Mapping reductions
Flashcards
Basic definitions
Suppose $L _ 1$ and $L _ 2$ are languages. @Define what it means for $L _ 1$ to be mapping reducible to $L _ 2$, i.e. $L _ 1 \le _ m L _ 2$.
There exists a computable function $f : \Sigma^\ast \to \Sigma^\ast$ such that $w \in L _ 1$ iff $f(w) \in L _ 2$.
Suppose:
- $L _ 1, L _ 2$ are both languages
- $L _ 2$ is decidable
- $L _ 1 \le _ m L _ 2$
@State a result about decidability in this context.
$L _ 1$ is also decidable.
Suppose:
- $L _ 1, L _ 2$ are both languages
- $L _ 2$ is recursively enumerable
- $L _ 1 \le _ m L _ 2$
@State a result about recursive enumerability in this context.
$L _ 1$ is also recursively enumerable (note that this property is not true for Turing reductions).
Polynomial time reductions
Suppose $L _ 1$ and $L _ 2$ are languages. @Define what it means for $L _ 1$ to be polynomial-time mapping reducible to $L _ 2$, i.e. $L _ 1 \le _ m^\text{poly} L _ 2$.
There exists a polynomial time computable function $f : \Sigma^\ast \to \Sigma^\ast$ such that $w \in L _ 1$ iff $f(w) \in L _ 2$.
@State and @justify an intuitive result that says $\mathsf P$ is closed under poly-time reductions.
If $L _ 1 \in \mathsf P$ and $L _ 2 \le _ m^\text{poly} L _ 1$, then $L _ 2 \in \mathsf P$.
Proof: To check if $x \in L _ 2$, apply $f$ on $x$ to obtain $f(x)$. Then apply a polynomial time machine for $L _ 1$ to $f(x)$ to determine if $f(x) \in L _ 1$.