NP (complessità)
La classe di problemi 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 può essere definita in modo alternativo andando a sfruttare le macchine di Turing non deterministiche. Infatti si avrà che dato come un insieme di parole su un alfabeto , allora è nella classe se e solo se esiste una macchina di Turing non deterministica di complessità polinomiale che, per ogni input , ha almeno una computazione che converge.
In sostanza qualora esiste una macchina di Turing non deterministica che accetta (quindi converge per ogni input ).
Presa una macchina di Turing non deterministica di complessità polinomiale, allora essa accetterà un linguaggio il quale sarà un problema che appartiene alla classe . 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 che si fornisce alla macchina di Turing che accetta non appartiene a quest'ultimo linguaggio, allora si avranno solo computazioni infinite o computazioni massimali non accettanti.
Si ha che . 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 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 un linguaggio ossia un problema. Allora avremo che se e solo se esistono un problema di classe () ed un polinomio tali che il nostro problema può venire espresso come:
{, con tale che T}
In buona sostanza il teorema ci fa capire che il problema è nella classe se esiste un problema della classe (problema accettato da una macchina di Turing deterministica, che chiamiamo , in un tempo polinomiale) tale che per ogni l'input viene accettato da in tempo polinomiale, con il vincolo che la lunghezza di sia polinomialmente limitata da.
Quest'ultima condizione sulla lunghezza di è 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 accetti in tempo polinomiale. Dunque in buona sostanza possiamo affermare che se e solo se per ogni sono in grado di associargli una possibile soluzione che so verificare in un tempo polinomiale.
Dimostrazione
[modifica | modifica wikitesto]Verso se del teorema) Supponiamo di avere un linguaggio della classe che viene deciso dalla macchina di Turing deterministica ed inoltre supponiamo sia vera la condizione vista nel teorema. Allora noi dovremo costruire la macchina di Turing non deterministica (che accetta ) in modo che per ogni input faccia i seguenti 3 passi:
- Calcola
- Scrive in modo non deterministico (ossia genera tutte le configurazioni) con
- Calcola la macchina per l'input
La prima osservazione che si può fare è che la macchina non deterministica ha complessità polinomiale in quanto tutti e tre i passi che essa deve svolgere sono tali. Dunque .
Inoltre osserviamo che se vale ed allora la computazione di si arresta. Pertanto ricaviamo che se valgono le \in T e ed , allora accetta . Ma se (macchina di Turing non deterministica di complessità polinomiale) accetta , significa che .
Verso e solo se del teorema) In sostanza occorre mostrare che se , ossia se è accettato da una macchina non deterministica di complessità polinomiale, allora vale che , T e che .
Per far ciò mi devo costruire il linguaggio in modo appropriato. A tale scopo supponiamo che sia la macchina non deterministica che accetta . 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:
{ ove codifica una computazione di che termina su l'input }
che come possiamo vedere danno vita all'insieme linguaggio . Di tale linguaggio va verificata l'appartenenza alla classe di problemi . A tale scopo bisognerà controllare che per l'input la computazione si arresti veramente.
In sostanza va verificato che al primo passo ci si trovi nello stato con scritto sul nastro l'input ; 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 tale che . A tale scopo osserviamo che se la computazione su di 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 ; inoltre anche avrà lunghezza polinomiale rispetto a . Dunque avremo il polinomio richiesto.