# Riduzione

::: warning
aggiungere esempi pratici
:::

$A$ è riducibile in $B$ (indicato come $\leq_r$) se e solo se esiste una funzione, totale e computabile, tale che, per ogni $x$, $x \in A$ se solo se $t(x) \in B$

## Proprietà di $\leq_r$
1. $\leq_r$ è riflessiva e transitiva
2. $A \leq_r B$ implica $\bar A \leq_r \bar B$
3. Se $A \leq_r B$ e $B$ è ricorsivo, allora $A$ è ricorsivo
4. Se $A \leq_r B$ e $B$ è ricorsivamente enumerabile, allora $A$ è ricorsivamente enumerabile

Esprimendo la stessa idea in un ambito meno formale si può dire che se si riesce a trovare un metodo algoritmico per costruire una soluzione del problema P partendo da una soluzione del problema P' (quindi riduco P in P') si possono dedurre queste due affermazioni
- Se P' è risolvibile, lo è anche P
- Se P è irrisolvibile, lo è anche P'

---
- conosco un problema indecidibile che è un caso particolare del mio problema
- il mio problema è indecidibile
- conosco un problema decidibile di cui il mio problema è un caso particolare
- il mio problema è decidibile