[8 febbraio 2024] Complessità

[Antaarees]

[Exyss]

Per il primo punto, ripropongo la soluzione presente sui miei appunti:

---

La dimostrazione richiesta nel secondo punto è presente sul libro di testo. La seconda parte della dimostrazione invece abbiamo che:

[Elia-Belli]

Teorema

$$4COL\leq_m^p SAT$$

Dimostrazione
Per il Teorema di Cook-Levin sappiamo che $SAT\in NP-Complete$ , quindi $\forall L\in NP,\ L\leq_m^p SAT$ .

Di conseguenza basta mostrare che $4COL\in NP$, ad esempio descrivendo un verificatore polinomiale $V$ su input $<G,y>$:

1. Interpreta $y=(c_1,c_2,\dots,c_n)$ come una 4-colorazione per $G$, con $c_i\in \{C,M,Y,K\}$, se non è una 4-colorazione rifiuta
2. Verifica $y$ sia una 4-colorazione valida: $\forall (i,j)\in E(G)$ verifica $c_i\neq c_j$, altrimenti rifiuta
3. Accetta

La complessità di tempo è ovviamente polinomiale $\Rightarrow V$ è un verificatore polinomiale per $4COL\ \ \square$