Penso che la domanda si riferisca al problema P = NP, per la cui soluzione il Clay Mathematics Institute offre un premio di 1 milione di dollari.

Le sigle P e NP si riferiscono a due classi di problemi decisionali, quelli Polinomiali e quelli Nondeterministicamente Polinomiali. Un problema decisionale è un problema che ammette come risposta soltanto sì oppure no.

Chiameremo nel seguito P1 e P2 questi due classici problemi decisionali:
P1 : "Dato un numero intero positivo A, dire se A è primo".
P2 : "Dati un insieme A di interi positivi ed un intero positivo S, dire se esiste un sottoinsieme B di A tale che la somma degli elementi di B sia S".

In generale un problema decisionale consiste di una infinità di domande possibili, che vengono dette istanze del problema.

Per esempio:
domanda 1 = "53683450179727641727 è primo?"
domanda 2 = "17723114348029997127 è primo?"
sono due istanze del problema P1.
Ecco invece una istanza del problema P2:
domanda 3 = "Esiste un sottoinsieme B di A = {2, 4, 9, 13, 17, 23, 32, 70, 123, 157} tale che la somma dei suoi elementi sia 228?"

Una istanza contiene dati ai quali si assegna un peso p. Per il problema P1, il peso p è il numero delle cifre (essenzialmente il logaritmo in base 10, Log(A), di A) dell'intero A.
Per il problema P2, il peso p è il numero degli elementi |A| dell'insieme A.

Per risolvere un problema decisionale si costruiscono appositi algoritmi. Generalmente esistono sempre algoritmi che sono in grado di rispondere a qualsiasi istanza del problema: gli algoritmi di forza bruta, che esplorano tutto lo spazio di ricerca dei dati. Per esempio alla domanda 1 si può tentare di rispondere dividendo 53683450179727641727 per tutti gli interi dispari che lo precedono. Un algoritmo molto più intelligente, ma purtroppo inefficace per numeri così grandi, consiste nel dividere A per tutti i primi non maggiori della radice quadrata di A. Per rispondere alla domanda 3 si possono considerare tutti i 2¹⁰ sottoinsiemi di A. Poiché 2¹⁰ = 1024, questo lavoro può essere eseguito in un istante da un computer. Però se il peso dei dati passa da 10 a 100, cioè |A| = 100, ci sono 2¹⁰⁰ sottoinsiemi, e le cose si complicano un tantino…

Ovviamente il tempo T di esecuzione di un algoritmo che risponde ad una data istanza del problema è una funzione del peso dei dati, T = T(p).

Facciamo un esempio concreto, per il problema P2, sempre pensando all'algoritmo di forza bruta. Se siamo in grado di eseguire la somma di un sottoinsieme B di A in un microsecondo (10^-6 s) con p = 10 impieghiamo circa un millisecondo a rispondere. Se p = 100, poiché 2¹⁰⁰ vale circa 10³⁰, occorreranno, nel caso peggiore, approssimativamente 10²⁴ secondi, ovvero qualcosa come 3 x 10¹⁶ anni (trenta milioni di miliardi di anni).

La classe P è formata dall'insieme dei problemi decisionali Q per i quali esiste un algoritmo che risponde in tempo polinomiale.

Questa è una delle cose più importante da capire. Diciamo che un algoritmo V risponde in tempo polinomiale al problema decisionale Q se, data una qualsiasi istanza d di Q, V risponde sì o no in un ammontare di tempo che è minore di p^k, dove p è il peso di d. L'esponente k deve essere una costante, legata al problema Q ma indipendente dalla istanza d di Q.

Uno dei risultati matematici più importanti dell'inizio millennio (2002), dovuto ai tre matematici indiani Agrawal, Kayal e Saxena, è che P1 appartiene a P, ovvero:

Primes is in P

Siamo quindi in grado di decidere se un numero N è primo in un ammontare di tempo che è proporzionale a una potenza del numero delle cifre (Log(n)) di N, e non a N stesso (o alla sua radice quadrata)! La differenza è abissale, inimmaginabile. Per quanto riguarda P2, non sono noti algoritmi polinomiali che lo risolvano. Questo però non significa che tali algoritmi non esistano.

Veniamo ora alla classe NP. Consideriamo un problema decisionale Q. Supponiamo che ci sia un oracolo, il quale risponde immediatamente sì o no ad ogni istanza di Q. Non solo. L'oracolo sa che siamo gente incredula, che non si fida di nessuno, e quindi ci offre addirittura un certificato di garanzia, un modo di verificare la correttezza della sua risposta. Per esempio, per il problema P2, alla domanda 3 risponde "Sì, esiste un sottoinsieme B di A la cui somma è 228." A questa risposta allega il certificato "B = {9, 13, 17, 32, 157}". A noi resta solo l'onere di verificare la correttezza della risposta, ovvero di sommare B.

Diciamo che un problema Q appartiene alla classe NP se siamo in grado di verificare in tempo polinomiale la correttezza di ogni risposta sì che ci viene data dall'oracolo, esaminando l'allegato certificato.

La grandezza dello spazio di ricerca è sparita, nella classe NP ! Non ci sono più, per tornare al nostro esempio, 10³⁰ somme da fare, ma soltanto una! Ovviamente la classe P e contenuta nella classe NP . Sembrerebbe ovvio che NP sia assai più grande di P. Moltissimi difficili problemi matematici di ottimizzazione stanno in NP , ma non è noto per essi alcun algoritmo che li risolva in tempo polinomiale. Molti di questi problemi come quello del Commesso Viaggiatore, sono di grande utilità pratica. Il problema del commesso viaggiatore è quello di trovare un percorso ottimale (di costo minimo), ma può essere messo sotto forma di problema decisionale così:

Istanza: N città, con relativa carta stradale che indica le connessioni, e elenco dei costi dei percorsi che congiungono le città adiacenti. È dato inoltre il costo massimo M che il commesso viaggiatore è disposto a pagare.
Il peso della istanza è N.
Domanda: "Esiste un percorso che tocca ogni città una e una sola volta con costo complessivo minore di M?"

Non sono noti algoritmi polinomiali che risolvano il problema del commesso viaggiatore. Esso sta ovviamente in NP : se la soluzione esiste l'oracolo ci dà un circuito funzionante, e a noi basta sommare i costi per verificare l'esattezza della soluzione.
Ci manca ancora un ingrediente. I problemi NP-completi.

Un problema Q si dice NP-completo se

1. Q appartiene alla classe NP .
2. Dati un problema P in NP e una istanza qualsiasi d di P, si può trasformare d in una istanza d' di Q, e si può trasformare una risposta a d' in una risposta a d. Le trasformazioni devono avvenire in tempo polinomiale.

In sostanza un problema Q in NP è NP-completo se il saper risolvere Q ci permette di risolvere qualsiasi altro problema in NP ! Si noti che se sapessimo risolvere un problema NP-completo in tempo polinomiale, sapremmo risolvere tutti i problemi di NP in tempo polinomiale, e quindi NP verrebbe a coincidere con P!

Sorge un legittimo dubbio: esistono problemi NP-completi? La risposta è sì. Il primo è stato scoperto da Stephen Cook nel 1971. Da allora ne sono stati trovati centinaia, in tutti i settori della matematica e della informatica, comprendenti importantissimi problemi combinatoriali e di ottimizzazione, di grande rilevanza applicativa.

Tra i problemi NP-completi ci sono anche il nostro P2 (detto usualmente "Knapsack problem", o "problema del fusto" o "dello zaino") e il problema del commesso viaggiatore.

Dunque chiunque riesca a trovare un algoritmo che "risolva in fretta", cioè in tempo polinomiale, ogni istanza di un problema NP-completo otterrebbe:

1. Fama imperitura.
2. 1 milione di dollari dal Clay Mathematics Institute.
3. La soluzione efficace e simultanea di moltissimi problemi estremamente difficili.
4. La dimostrazione di quello che pare assurdo: dell'oracolo non sappiamo che farcene!

Torniamo infine alla domanda posta all'inizio.

Gauss, da bambino, provò che 1 + 2 + 3 + … + n = n(n+1)/2. Fece questo a scuola per evitare di annoiarsi mortalmente calcolando 1 + 2 + 3 + … + 100, come richiesto (per punizione) alla scolaresca dal maestro, forse stanco della generale distrazione. In effetti l'algoritmo "stupido" per trovare la somma degli interi da 1 ad n, non è polinomiale, secondo la usuale accezione del termine, perché lavora in un tempo che è proporzionale ad n stesso e non ad una potenza di Log(n). Invece l'algoritmo "furbo" di Gauss trova la soluzione con un singolo prodotto che richiede un tempo proporzionale a Log(n)². Il fatto però che si riesca a risolvere qualcosa in fretta, non basta, come spero sia chiaro a chi è arrivato fin qui, a provare P = NP . Gauss avrebbe dovuto cimentarsi, per esempio, con questo problema (che è una versione scherzosa dello "knapsack"):Istanza: Sono dati

1. Un ladro maniacale che vuole riempirsi lo zaino con esattamente S chili di oro.
2. n pezzi di peso diverso dello splendente metallo.

Domanda: Ce la farà il ladro, prima che sia troppo tardi?

È oggi di gran moda il Sudoku, gioco che dopo avere appassionato il Giappone per due decenni ha invaso gli USA ed infine è approdato in Europa. C'è su molti giornali la razione quotidiana, o settimanale, di Sudoku. I gioco viene presentato come una tavola 9x9, suddivisa in 9 quadrati 3x3, nella quale sono scritte alcune cifre diverse da zero, cioè interi compresi tra 1 e 9. Si vince completando la tavola con altre cifre non nulle in modo tale che:

1. In ogni riga ed in ogni colonna della matrice grande, ogni cifra appaia una ed una sola volta.
2. In ogni quadratino 3x3 appaiano le 9 cifre.

Vediamo un esempio:

Siete pronti? Generalizzaziamo il Sudoku, e al tempo stesso definiamo il Problema del Sudoku.

Una istanza del problema del Sudoku è una tavola G n² x n², suddivisa in n² quadratini n x n, contenente alcuni interi compresi tra 1 e n². Il peso della istanza è n.
La domanda è: "si può completare G in modo tale che in ogni riga ed in ogni colonna di G gli interi tra 1 e n² appaiano una ed una sola volta, e siano al tempo stesso tutti presenti in ogni quadratino?

Ovviamente il problema sta in NP. Se la risposta è sì l'oracolo ci dà come certificato la tavola G completata, e facciamo in fretta a controllare.

Un esempio con n = 2:

Science and Information Science presso l'Università di Tokio, ha dimostrato nel 2003 che il problema del Sudoku è NP-completo!

Ecco, se Gauss ci ispirasse un algoritmo deterministico e polinomiale per risolverlo...

La congettura P=NP riguarda la complessità dei problemi decisionali, vale a dire dei problemi che riguardano l'esistenza di algoritmi per risolvere una data classe di questioni. Ad esempio: è un quadrato perfetto il numero n ? È un numero primo? Oppure, quali sono i fattori primi di n ? e così via.

Naturalmente, la complessità del problema è legata alla richiesta delle risorse che sono necessarie per dare la risposta nel caso generale. Tipicamente, con una formalizzazione precisa – necessaria anche solo per esprimere la problematica – ci si riferisce al tempo di calcolo, inteso come numero di passi in funzione della lunghezza dell'input, di cui ha bisogno un modello formale di calcolatore per dare una risposta.

Si dice che un problema appartiene alla classe P oppure alla classe NP per intendere che si può risolvere in "tempo polinomiale", vale a dire un tempo che cresce in maniera polinomiale rispetto alla lunghezza dell'input, nel primo caso mediante un algoritmo deterministico, nel secondo mediante un algoritmo non deterministico (intuitivamente, quando ad ogni stadio si hanno più possibilità di operazione). Ovviamente la classe P è contenuta in NP e il problema che si pone è quello di verificare se le due classi coincidono oppure sono distinte: intuitivamente, i problemi P sono considerati accessibili alle risorse di calcolo (e lo sono di fatto per polinomi di grado non troppo elevato), mentre quelli NP sono inaccessibili.

Per proseguire con gli esempi dati in precedenza: il problema dei quadrati perfetti è in P, mentre soltanto pochi anni fa ha destato grande scalpore la scoperta che anche il problema della primalità di n è in P. Quanto al problema della scomposizione in fattori primi, non è noto se sia in P e qualche ricercatore sostiene che sia un tipico problema NP.

La domanda del lettore sembra collegare la congettura P=NP a una formula attribuita a Gauss (secondo alcuni trovata quando frequentava le scuole elementari) che, in maniera completa rispetto a quanto cita il lettore, dice che la somma dei primi n interi è uguale a n(n+1)/2.

In questo caso, la formula risolve un problema P: la somma dipende infatti dal quadrato di n. Ma questo è solo un caso particolare, mentre la congettura riguarda il problema generale e coinvolge molti argomenti di logica e di teoria degli algoritmi (che, per forza di cose, Gauss non poteva formulare).

Comunque, personalmente sarei anch'io d'accordo nell'assegnare a Gauss qualsivoglia premio per la matematica del (passato) millennio.