Introduzione ai problemi di complessità, P e NP, commesso viaggiatore.

Quando si affrontano certi tipi di problemi non conta soltanto che la soluzione proposta sia corretta, ma anche che sia efficiente, ovvero che la complessità delle operazioni da svolgere non aumenti troppo in funzione dei dati iniziali.

In questa lezione si trattano la fondamentali differenze tra algoritmi di tipo esponenziale e di tipo polinomiale, come velocità di esecuzione e dipendenza dal dato di input.
Vengono poi introdotte informalmente le classi di problemi P, NP e NP-C (NP-Completo) sottilineando l'importanza di quest'ultima per affrontare problemi ancora oggi senza una soluzione definitiva. Tra questi si introduce il problema: P = NP ?

Come esempio guida per introdurre tutti questi concetti è stato usato il famoso ed intuitivo gioco del Sudoku.