Controllare se una lista di parole è o non è in ordine alfabetico è un compito facile per una macchina. Basta confrontare le iniziali di tutte le coppie successive di parole e vedere se siano o meno in ordine alfabetico. Anche mettere in ordine le parole di una lista è facile, il tempo necessario va come il quadrato del numero degli item della lista. Ma non tutti i problemi sono così facili. Ad esempio, verificare se un enunciato del calcolo proposizionale sia o meno una tautologia è difficile, come sanno gli studenti, perché è sì proporzionale alla lunghezza della formula, ma se n sono le lettere proposizionali va come 2 elevato alla n. Si dice anche che il tempo è esponenziale.
C’è un’ampia categoria di problemi tali che controllare se la soluzione sia corretta sono facili, ma trovare la soluzione è difficile. Ad esempio, verificare se una schedina di sudoku è corretta è facile, mentre trovare la soluzione sembra difficile.
Di solito si indicano come exptime i problemi per i quali controllare la soluzione è difficile. E si indicano con NP i problemi per i quali controllare la soluzione è facile. Quelli come la lista si chiamano invece P. Alcuni pensano che tutti i problemi NP siano anche P, ma noi per adesso sappiamo che molti problemi NP sono “difficili”, cioè non c’è un algoritmo facile per risolverli, anche se ce ne è uno facile per verificare se una soluzione sia corretta.
Vi ricordate Candy Crush? Il gioco più giocato su Facebook? Ecco Candy Crush è NP difficile, cioè data una distribuzione di caramelle su una tabella, è facile controllare se viene rispettata la regola delle tre caramelle in fila, ma trovare una soluzione è difficile.
Abbiamo già parlato di macchine e intelligenza artificiale, l’ultima delle volte qui.
Vincenzo Fano è docente ordinario di Logica e Filosofia della Scienza presso il corso di laurea magistrale in Filosofia dell’Informazione. Teorie e Gestione della Conoscenza dell’Università degli studi di Urbino Carlo Bo.