Calcoli deterministici e non deterministici
Per capire la classe P e NP, per prima cosa dovremmo conoscere il modello computazionale. Quindi, in questo capitolo discuteremo due importanti modelli computazionali.
Calcolo deterministico e classe P
Macchina di Turing deterministica
Uno di questi modelli è la macchina di Turing deterministica a nastro singolo. Questa macchina è composta da un controllo a stati finiti, una testina di lettura-scrittura e un nastro a due vie con sequenza infinita.
Di seguito è riportato il diagramma schematico di una macchina di Turing deterministica a nastro singolo.
Un programma per una macchina di Turing deterministica specifica le seguenti informazioni:
- Un insieme finito di simboli del nastro (simboli di input e un simbolo vuoto)
- Un insieme finito di stati
- Una funzione di transizione
Nell'analisi algoritmica, se un problema è risolvibile in tempo polinomiale da una macchina di Turing deterministica a nastro, il problema appartiene alla classe P.
Calcolo non deterministico e classe NP
Macchina di Turing non deterministica
Per risolvere il problema computazionale, un altro modello è la Macchina di Turing non deterministica (NDTM). La struttura di NDTM è simile a DTM, tuttavia qui abbiamo un modulo aggiuntivo noto come modulo di ipotesi, che è associato a una testina di sola scrittura.
Di seguito è riportato il diagramma schematico.
Se il problema è risolvibile in tempo polinomiale da una macchina di Turing non deterministica, il problema appartiene alla classe NP.