NP (complessità)

Da Wikipedia, l'enciclopedia libera.

[modifica] La classe NP

La classe di problemi NP comprende tutti quei problemi che hanno una complessità di tipo esponenziale ma che data una probabile soluzione, prevede un algoritmo di complessità polinomiale in grado di verificare se quella data è effettivamente una soluzione.

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 , ha almeno una computazione che converge.

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

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 avrà fra tutte le possibili computazioni su tale input, una che si arresta.

Invece se l'input w che forniamo alla macchina di Turing che accetta S non appartiene a quest'ultimo linguaggio, allora si avranno solo computazioni infinite e la macchina di Turing ovviamente diverge.

Ribadiamo inoltre ciò che . Da tale affermazione evinciamo innanzitutto che tutti i problemi di classe P sono anche problemi di classe NP.

A questo punto facciamo vedere che la classe NP può essere caratterizzata come quella classe di problemi per i quali siamo in grado di verificare in modo rapido se una possibile soluzione è effettivamente tale.

[modifica] Teorema

Sia un linguaggio ossia un problema. Allora avremo che se e solo se esistono un problema T di classe P () ed un polinomio p_s tali che il nostro problema S può venire espresso come:

S = {, con tale che 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 non deterministica, che chiamiamo M_t, in un tempo polinomiale) tale che per ogni l'input viene accettato da M_t in tempo polinomiale, con il vincolo che la lunghezza di y sia polinomialmente limitata daw.

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 e che quindi M_t accetti T in tempo polinomiale. Dunque in buona sostanza possiamo affermare che se e solo se per ogni sono in grado di associargli una possibile soluzione y che so verificare in un tempo polinomiale.

[modifica] 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 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) con
3. Calcola la macchina M_t per l'input

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 ed \in T allora la computazione di M_t si arresta. Pertanto ricaviamo che se valgono le \in T e ed , allora M accetta S. Ma se M (macchina di Turing non deterministica di complessità polinomiale) accetta S, significa che .

Verso e solo se del teorema) In sostanza occorre mostrare che se , ossia se S è accettato da una macchina non deterministica di complessità polinomiale, allora vale che , T e che .

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₀ con scritto sul nastro l'input w; poi bisogna verificare che ogni configurazione successiva derivi dalla precedente mediante la funzione di transizione δ; infine va verificato che l'ultima configurazione sia una configurazione di tipo terminale. Se tutto ciò è vero allora .

A questo punto va fatto vedere che esiste un polinomio p_s tale che . 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.

Classi di complessità (elenco)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH