# Notes - Computational Complexity HT25, Mapping reductions

> Source: https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/mapping-reductions/ · Updated: 2025-03-25 · Tags: uni, notes

- [Course - Computational Complexity HT25](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/)
	- [Notes - Computational Complexity HT25, Basic definitions](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/basic-definitions/)
	- [Notes - Computational Complexity HT25, Turing reductions](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/turing-reductions/)
	- [Notes - Computational Complexity HT25, Non-deterministic Turing machines](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/non-deterministic-turing-machines/)
	- See also:
	- [Notes - ADS HT24, NP-hardness and NP-completeness](https://ollybritton.com/notes/uni/part-a/ht24/ads/notes/np-hardness-and-np-completeness/)

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

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt