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




Related posts