NP (complessità)

Da Wikipedia, l'enciclopedia libera.

La classe di problemi NP comprende tutti quei problemi decisionali che, per verificare la correttezza di una data 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 e la macchina di Turing ovviamente diverge.

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[modifica | modifica wikitesto]

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^*, \exists y \in A^* con |y| \leq p_s (|w|) tale che w \sharp 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 \sharp 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[modifica | modifica wikitesto]

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| \leq 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 \sharp y con |y| \leq p_s (|w|)
  3. Calcola la macchina M_t per l'input w \sharp 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| \leq p_s (|w|) ed w \sharp y \in T allora la computazione di M_t si arresta. Pertanto ricaviamo che se valgono le w \sharp y \in T e |y| \leq 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 \sharp y \in T e che |y| \leq 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| \leq 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[modifica | modifica wikitesto]