Supponiamo che tu stia organizzando alloggi per un gruppo di quattrocento studenti universitari. Lo spazio è limitato e solo un centinaio di studenti riceveranno posti nel dormitorio. Per complicare le cose, il Preside ti ha fornito un elenco di coppie di studenti incompatibili e ha chiesto che nessuna coppia di questa lista appaia nella tua scelta finale., Questo è un esempio di ciò che gli informatici chiamano un problema NP, poiché è facile verificare se una determinata scelta di cento studenti proposta da un collega è soddisfacente (cioè, nessuna coppia presa dalla lista del tuo collega appare anche nella lista dall’ufficio del Preside), tuttavia il compito di generare una tale lista da zero sembra essere così difficile da essere completamente impraticabile. In effetti, il numero totale di modi per scegliere cento studenti tra i quattrocento candidati è maggiore del numero di atomi nell’universo conosciuto!, Quindi nessuna civiltà futura potrebbe mai sperare di costruire un supercomputer in grado di risolvere il problema con la forza bruta; cioè controllando ogni possibile combinazione di 100 studenti. Tuttavia, questa apparente difficoltà può riflettere solo la mancanza di ingegno del programmatore. In effetti, uno dei problemi in sospeso nell’informatica è determinare se esistono domande la cui risposta può essere controllata rapidamente, ma che richiedono un tempo incredibilmente lungo per risolvere con qualsiasi procedura diretta., Problemi come quello sopra elencato sembrano certamente di questo tipo, ma finora nessuno è riuscito a dimostrare che nessuno di loro è davvero così difficile come appaiono, cioè che non esiste davvero un modo fattibile per generare una risposta con l’aiuto di un computer. Stephen Cook e Leonid Levin formularono il problema P (cioè facile da trovare) contro NP (cioè facile da controllare) indipendentemente nel 1971.
Immagine di credito: a sinistra, Stephen Cook di Jiří Janíček (ritagliata). CC BY-SA 3.0