Vi sarà senz'altro capitato di ricevere un grosso mazzo di chiavi per aprire la porta di una casa di villeggiatura. Tipicamente, le chiavi sono molto simili tra loro e ogni volta dovete provarne alcune prima di indovinare quella giusta. Questa irritante situazione esemplifica uno dei più grandi problemi dell'informatica teorica, noto sotto la criptica dicitura P vs. NP. L'Istituto matematico Clay lo classifica tra i sette "problemi del millennio" e offre un milione di dollari a chi lo risolve.
Cosa c'è di così cruciale in un problema apparentemente banale come quello delle chiavi? E' questo: si tratta di una situazione in cui ciascun singolo tentativo di apertura può essere effettuato in un tempo definito secondo una semplice sequenza di operazioni (si dice quindi polinomiale e si indica con P), tuttavia non esiste alcun metodo per trovare la chiave giusta in un tempo altrettanto definito, per cui, nel suo complesso, la soluzione è non-deterministica (scritto NP). Il cruccio degli informatici è sapere se i problemi di tipo NP si possano nella generalità riportare a problemi di tipo P, o se questo sia inerentemente impossibile. Nel nostro esempio, la riduzione avverrebbe se fosse possibile un "colpo d'occhio" in grado di individuare la chiave giusta nel mazzo, per mazzi arbitrariamente grandi.
Una semplice curiosità? Tutt'altro: sull'irriducibilità dei problemi di tipo NP a problemi di tipo P si gioca, ad esempio, la sicurezza informatica. I "mazzi di chiavi" che si ottengono con certi metodi di criptazione sono così grandi che non basterebbe una vita per trovare la chiave giusta.
L'estate dei nerd di tutto il mondo è stata resa molto calda dalla notizia che un ricercatore indiano, Vinay Deolalikar, avrebbe dimostrato che NP è irriducibile a P. Niente "colpi d'occhio", insomma. Sul fatto che le cose siano in effetti così si hanno pochi dubbi: in caso contrario infatti quasi tutti i problemi si potrebbero automaticamente risolvere e la vita perderebbe molto del suo charme. Ma, si sa, ai nerd le congetture non piacciono, le dimostrazioni invece sì, di qui l'eccitazione estiva.
La comunità scientifica è attualmente al vaglio della prova di Deolalikar, e sembra, purtroppo, che questa abbia alcuni difetti. Tuttavia, molti affermano che il problema sia vicino ad una soluzione. Il giorno in cui una dimostrazione valida sarà fornita, sarà interessante vedere se questa abbia qualche risvolto filosofico. La prova di Goedel sull'incompletezza semantica dei linguaggi formali di una certa espressività, ad esempio, ci ha ricordato le insidie che vengono dal parlare di linguaggio col linguaggio stesso, cosa che per inciso continuiamo a fare tutti i giorni, talvolta anche con discreto successo. Cosa ci insegnerà la prova di Deolalikar o chi per esso?
