Immagina una scacchiera. Posiziona due regine rivali in modo che non possano attaccarsi direttamente. Facile? Bene, ora ripeti il processo aggiungendo altre sei regine. Complicato, ma possibile. Per finire, estendi il problema a scacchiere di qualsiasi dimensione, con qualsiasi numero di regine preimpostate. Il cosiddetto «problema delle 1000 regine» non è altro che un esempio isolato per spiegare un esercizio molto più complesso, «P versus NP», a tal punto che il Clay Mathematics Institute offre un milione di dollari per la prima dimostrazione positiva.
I Sette Problemi del Millennio
Esiste una competizione molto interessante chiamata «I Sette Problemi del Millennio». Iniziata nel 2000 dal Clay Mathematics Institute, il suo obiettivo è trovare risposte a sette problemi classici che hanno resistito a una soluzione con il passare degli anni. Finora, l'unico problema che ha ricevuto una dimostrazione appropriata è la «Congettura di Poincaré», sviluppata dal matematico russo Grigori Perelman.
L'istituto non ha esitato a offrirgli un milione di dollari per il suo lavoro, ma Perelman lo ha rifiutato, dicendo che il suo contributo non era stato maggiore di quello del matematico Richard S. Hamilton, che aveva suggerito una soluzione in precedenza. Un altro dei grandi problemi che l'istituto desidera vedere risolto è il famoso «P versus NP», e per cercare di capirlo, la cosa più comune è ricorrere agli scacchi:
Non è stato d'aiuto? Non preoccuparti, all'inizio non è servito molto neanche a me. P versus NP è più complicato che lanciare un paio di regine su una scacchiera, e la sua reputazione di impossibile è ben giustificata. In termini molto rilassati (e dico «rilassati» con tutta sincerità) possiamo dire che i problemi chiamati P sono facili da risolvere e verificare con algoritmi, entro un «tempo polinomiale».
D'altra parte, i problemi NP sono facili da verificare se la loro soluzione è corretta o meno, mentre arrivarci richiede molto tempo e sforzo, con notevoli perdite di efficienza. Esempi robusti di problemi NP sono i puzzle, il Sudoku e persino il Campo minato. Ora: cosa succederebbe se trovassi la chiave per risolvere un problema NP in tempo polinomiale, con grande efficienza?
Se ci riesci, scoprirai che non ci sono differenze tra N e NP (N = NP), facendo sì che il Clay Institute (e non l'Università di St Andrews come è stato ripetuto fino allo sfinimento) lanci un milione di dollari nella tua direzione, probabilmente seguito da un premio Nobel e dall'odio degli esperti di crittografia in tutto il mondo. La maggior parte degli esperti è propensa a N ≠ NP, e a dire il vero molte cose dipendono da questo (il cifrario menzionato prima è una). Ma se hai intenzione di provarci comunque... buona fortuna. Ne avrai bisogno.
