Teoria della complessità computazionale: differenze tra le versioni

* <math>\mbox{NP} = \cup_{k>0} \mbox{NTIME}(n^k)</math>; per questi problemi sono noti algoritmi che terminano in un numero di passi polinomiale rispetto alla dimensione dei dati ''nel caso si possa utilizzare un numero indeterminato di macchine in parallelo'', o nel caso si utilizzi una macchina di Turing ''non deterministica'' (come da definizione). Altre formulazioni equivalenti sono affermare che l'algoritmo termina in tempo polinomiale con l'"algoritmo di Gastone" (ogni volta che si deve fare una scelta, si indovina sempre la strada corretta), oppure che la ''verifica'' di una soluzione può essere effettuata in tempo polinomiale. La sigla NP sta per ''non-deterministic polinomial'' (polinomiale nondeterministico): pensarloe comenon per "non polinomiale" è sbagliato, anche se èper veromolti chedi tuttiessi glinon algoritmisi realizzabiliconoscono suche calcolatorialgoritmi fisicideterministici risolvono questi problemiche inimpiegano tempo esponenziale rispetto a <math>n</math>. A questa classe appartiene una gran quantità di problemi di interesse applicativo.