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




Related posts