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$.