NP (complessità)

Diagramma di Eulero-Venn per le classi di complessità P, NP, NP-completo e NP-hard

La classe di problemi $NP$ comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale. La classe NP prende il suo nome dall'abbreviazione di Nondeterministic Polynomial Time.

La classe $NP$ può essere definita in modo alternativo andando a sfruttare le macchine di Turing non deterministiche. Infatti si avrà che dato $S$ come un insieme di parole su un alfabeto $A$, allora $S$ è nella classe $NP$ se e solo se esiste una macchina di Turing non deterministica di complessità polinomiale $M$ che, per ogni input $w\in S$, ha almeno una computazione che converge.

In sostanza $S\in NP$ qualora esiste una macchina di Turing non deterministica che accetta $S$ (quindi converge per ogni input $w\in S$).

Presa una macchina di Turing non deterministica di complessità polinomiale, allora essa accetterà un linguaggio $S$ il quale sarà un problema che appartiene alla classe $NP$. Tale macchina di Turing dunque, per ogni input $w\in S$ avrà fra tutte le possibili computazioni su tale input, una che si arresta.

Invece se l'input $w$ che si fornisce alla macchina di Turing che accetta $S$ non appartiene a quest'ultimo linguaggio, allora si avranno solo computazioni infinite o computazioni massimali non accettanti.

Si ha che $P\subseteq NP$. Da tale affermazione si evince innanzitutto che tutti i problemi di classe P sono anche problemi di classe NP.

A seguito si mostra che la classe $NP$ può essere caratterizzata come quella classe di problemi per i quali si è in grado di verificare in modo rapido se una possibile soluzione è effettivamente tale.

Teorema di Proiezione

Sia $S\subseteq A^{*}$ un linguaggio ossia un problema. Allora avremo che $S\in NP$ se e solo se esistono un problema $T$ di classe $P$ ($T\in P$) ed un polinomio $p_s$ tali che il nostro problema $S$ può venire espresso come:

$S=${$w\in A^{*}$, $\mathrm{\exists }y\in A^{*}$ con $|y|\le p_s(|w|)$ tale che $w\mathrm{♯}y\in$ T}

In buona sostanza il teorema ci fa capire che il problema $S$ è nella classe $NP$ se esiste un problema $T$ della classe $P$ (problema accettato da una macchina di Turing deterministica, che chiamiamo $M_t$, in un tempo polinomiale) tale che per ogni $w,y\in A^{*}$ l'input $w\mathrm{♯}y$ viene accettato da $M_t$ in tempo polinomiale, con il vincolo che la lunghezza di $y$ sia polinomialmente limitata da$w$.

Quest'ultima condizione sulla lunghezza di $y$ è fondamentale per assicurare che il controllo sul fatto che essa sia una effettiva soluzione avvenga in tempo polinomiale.

Infatti non è sufficiente che $T\in P$ e che quindi $M_t$ accetti $T$ in tempo polinomiale. Dunque in buona sostanza possiamo affermare che $S\in NP$ se e solo se per ogni $w\in S$ sono in grado di associargli una possibile soluzione $y$ che so verificare in un tempo polinomiale.

Dimostrazione

Verso se del teorema) Supponiamo di avere un linguaggio $T$ della classe $P$ che viene deciso dalla macchina di Turing deterministica $M_t$ ed inoltre supponiamo sia vera la condizione $|y|\le p_s(|w|)$ vista nel teorema. Allora noi dovremo costruire la macchina di Turing non deterministica $M$ (che accetta $S$) in modo che per ogni input $w$ faccia i seguenti 3 passi:

1. Calcola $p_s(|w|)$
2. Scrive in modo non deterministico (ossia genera tutte le configurazioni) $w\mathrm{♯}y$ con $|y|\le p_s(|w|)$
3. Calcola la macchina $M_t$ per l'input $w\mathrm{♯}y$

La prima osservazione che si può fare è che la macchina non deterministica $M$ ha complessità polinomiale in quanto tutti e tre i passi che essa deve svolgere sono tali. Dunque $C_M(n)=O(n^k)$.

Inoltre osserviamo che se vale $|y|\le p_s(|w|)$ ed $w\mathrm{♯}y\in T$ allora la computazione di $M_t$ si arresta. Pertanto ricaviamo che se valgono le $w\mathrm{♯}y$ \in T e $|y|\le p_s(|w|)$ ed $y\in S$, $w\in S$ allora $M$ accetta $S$. Ma se $M$ (macchina di Turing non deterministica di complessità polinomiale) accetta $S$, significa che $S\in NP$.

Verso e solo se del teorema) In sostanza occorre mostrare che se $S\in NP$, ossia se $S$ è accettato da una macchina non deterministica di complessità polinomiale, allora vale che $T\in P$, $w\mathrm{♯}y\in$ T e che $|y|\le p_s(|w|)$.

Per far ciò mi devo costruire il linguaggio $T$ in modo appropriato. A tale scopo supponiamo che $M$ sia la macchina non deterministica che accetta $S$. Come sappiamo per una qualunque macchina, sia deterministica che non, ogni computazione è rappresentabile come una sequenza di configurazioni successive.

In particolare per ogni computazione convergente, avremo che la lista di configurazioni successive è una lista finita. Ad ognuna di queste sequenze di configurazioni possiamo associare un numero che nel nostro caso sarà binario.

Però per una macchina di Turing non deterministica, visto che infinite possono essere le possibili computazioni diverse che realizzo, si avranno problemi. Per ovviare a ciò possiamo andare a considerare le coppie:

$T=$ {$(w,y)$ ove $y$ codifica una computazione di $M$ che termina su l'input $w$}

che come possiamo vedere danno vita all'insieme linguaggio $T$. Di tale linguaggio $T$ va verificata l'appartenenza alla classe di problemi $P$. A tale scopo bisognerà controllare che per l'input $w$ la computazione si arresti veramente.

In sostanza va verificato che al primo passo ci si trovi nello stato $q_0$ con scritto sul nastro l'input $w$; poi bisogna verificare che ogni configurazione successiva derivi dalla precedente mediante la funzione di transizione $\delta$; infine va verificato che l'ultima configurazione sia una configurazione di tipo terminale. Se tutto ciò è vero allora $T\in P$.

A questo punto va fatto vedere che esiste un polinomio $p_s$ tale che $|y|\le p_s(|w|)$. A tale scopo osserviamo che se la computazione su $w$ di $M$ converge allora tale computazione ha un numero polinomiale di passi e ad ogni passo ho una configurazione che ha lunghezza polinomiale rispetto alla lunghezza di $w$; inoltre anche $y$ avrà lunghezza polinomiale rispetto a $w$. Dunque avremo il polinomio richiesto.

Voci correlate

• Classi di complessità P e NP
• P (complessità)

Collegamenti esterni

• Template:Collegamenti esterni