Classi decisionali

Le due classi principali sono la classe P, cioè l'insieme $\mathrm{P}$ di tutti i problemi decisionali $\mathcal{P}$ risolvibili in tempo polinomiale, e la classe NP, cioè l'insieme $\mathrm{NP}$ dei problemi che sono verificabili in tempo polinomiale.

Da queste definizioni si può quindi dedurre che $\mathrm{P}\subseteq \mathrm{NP}$.

Un problema è verificabile se esiste un algoritmo di verifica che ha come input un $i\in {\mathcal{I}}^{+}$ e un certificato, cioè una dimostrazione della soluzione. Si considera verificato se il certificato è una soluzione valida per $i$.

Di conseguenza, per i $\mathcal{P}\in \mathrm{NP}$ è facile verificare le istanze ${\mathcal{I}}^{+}$ e forse difficile verificare quelle ${\mathcal{I}}^{-}$.

Riducibilità

Le ulteriori classi dipendono dalla riducibilità polinomiale di due problemi ${\mathcal{P}}_1$ e ${\mathcal{P}}_2$, definita come: $${\mathcal{P}}_1{\le }_P{\mathcal{P}}_2$$ per cui esiste un algoritmo polinomiale che trasforma le istanze di ${\mathcal{P}}_1$ in istanze equivalenti di ${\mathcal{P}}_2$.

Per la riducibilità vale che la trasformazione deve mantenere la positività delle istanze, ed inoltre è:

• Riflessiva, ovvero riducibile a se stesso: $$\mathcal{P}{\le }_P\mathcal{P}$$

• Transitiva, ovvero riducibile a catena: $$\{\begin{array}{l}{\mathcal{P}}_1{\le }_P{\mathcal{P}}_2\\ {\mathcal{P}}_2{\le }_P{\mathcal{P}}_3\end{array}\Rightarrow {\mathcal{P}}_1{\le }_P{\mathcal{P}}_3$$

  Questo è dimostrabile perchè per ipotesi esistono gli algoritmi $$\begin{gathered} A_{12}:{\mathcal{I}}_1\to {\mathcal{I}}_2 \\ {A}_{23}:{\mathcal{I}}_2\to {\mathcal{I}}_3 \end{gathered}$$ e di conseguenza si può costruire $A_{13}$ come: $$\begin{array}{rl}{A}_{13}:{\mathcal{I}}_1& \to {\mathcal{I}}_3\\ i& \mapsto A_{23}(A_{12}(i))\end{array}$$

• Non sempre simmetrica, ovvero: $$\exists {\mathcal{P}}_{1,2}:{\mathcal{P}}_1{\le }_P{\mathcal{P}}_2\wedge \neg ({\mathcal{P}}_2{\le }_P{\mathcal{P}}_1)$$

Classe Co-NP

La classe Co-NP è l'insieme $\text{Co-NP}$ di tutti i problemi decisionali per cui il loro complemento è verificabile.

Il complemento di un problema $\bar{\mathcal{P}}$ è definito come il problema $\mathcal{P}$ in cui le istanze positive ${\mathcal{I}}^{+}$ si invertono di ruolo con le istanze negative ${\mathcal{I}}^{-}$, e quindi saranno queste ultime ad essere facili da verificare.

Classe NP-hard

La classe NP-hard è l'insieme $\text{NP-hard}$ di ogni problema decisionale $\mathcal{P}$ per cui vale che: $$\forall {\mathcal{P}}^{\prime }\in \mathrm{NP},{\mathcal{P}}^{\prime }{\le }_P\mathcal{P}$$ per cui i problemi sono almeno tanto difficili quanto quelli in $\mathrm{NP}$.

Classe NP-C

La classe NP-C è l'insieme $\text{NP-C}$ di ogni problema decisionale $\mathcal{P}$, detto NP completo, per cui vale che: $$\mathcal{P}\in \mathrm{NP}\wedge \mathcal{P}\in \text{NP-hard}$$ da cui si può ricavare il teorema fondamentale della NP completezza: $$\mathrm{P}\cap \text{NP-C}\ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}$$ anche se non è ancora stato trovato un problema dell'intersezione o provato che non ne esistono.

Si può dimostrare perchè per ipotesi $\exists \mathcal{P}\in \mathrm{P}\cap \text{NP-C}$ e, siccome $\mathcal{P}\in \text{NP-C}$ si ha che, per definizione ogni $Q\in \mathrm{NP}$ è riducibile a $\mathcal{P}$. Di conseguenza, dato che $\mathcal{P}\in \mathrm{P}$, anche $Q\in P$ e quindi $P=NP$.

Inoltre, dato un problema $\mathcal{P}\in \mathrm{NP}$ è possibile riconoscerlo NP completo se: $$\exists Q\in \text{NP-C}:Q{\le }_P\mathcal{P}$$ perchè ogni problema in $\mathrm{NP}$ è riducibile a $Q$, e quindi lo sono anche a $\mathcal{P}$ per la transitività.