I problemi del millennio, ridendoci sopra..
Pubblicato da Davide, Aggiornato martedì 18 dicembre 2007 6 Commenti »
Ho perso una serata a leggere i problemi del millennio senza capirci una mazza. Sono i grandi problemi aperti che riguardano principalmente le scienze matematiche, ma che hanno notevoli implicazioni anche negli altri campi: informatica, ingegneria.. Per chi riesce a risolverne uno, c’è in palio un premio da 1 milione di dollari.
Come ci sono capitato? Ne conoscevo uno solo: P contro NP, riguardante la teoria della complessità computazionale.
Il problema è riuscire a dimostrare o confutare il fatto che non esistono problemi NP o detto con termini diversi dimostrare che tutti i problemi NP possono essere resi di tipo P. Questa è una domanda molto importante per l’informatica teorica. Vedi teoria della complessità algoritmica per una discussione più completa.
Essenzialmente, la domanda P = NP si può riformulare così: se le soluzioni positive a problemi di tipo SI/NO possono essere verificate velocemente, ne segue che le risposte possono essere anche calcolate velocemente? Un esempio per avere un’idea di cosa ciò vuole dire. Dati due numeri grandi X e Y, potremmo chiederci se Y sia multiplo di un intero tra 1 e X, estremi esclusi. Per esempio potremmo chiederci se 69799 sia multiplo di un qualche intero tra 1 e 250. La risposta è SI, sebbene sia necessaria una discreta quantità di lavoro per scoprirlo a mano. D’altra parte, se qualcuno ci dicesse che la risposta è “SI, perché 223 è un divisore di 69799″, allora potremo velocemente verificare questo fatto con un’unica divisione. Verificare che un numero è un divisore di un altro è molto più semplice che trovare il divisore stesso partendo da zero. L’informazione necessaria a verificare una risposta positiva è anche chiamata certificato. Concludiamo così che dati i certificati giusti, le risposte positive ai nostri problemi possono essere verificate velocemente (cioè in tempo polinomiale) e questo è il motivo per cui il problema è in NP. Non è noto se questo problema è in P. Il caso particolare in cui X=Y è stato dimostrato essere in P nel 2002.
Ed ero curioso di vedere gli altri.. Se non avete niente da fare e la tv non offre altro che calcio, potete buttare via il vostro tempo leggendoli tutti. Ho tremendi ricordi di un esame passato pochi mesi fa.
Tanto per concludere (colpa dell’orario):
A Bologna organizzano un congresso per ingegneri e matematici. Vengono invitati gli ingegneri ed i matematici di Pisa. Arrivati alla stazione i matematici, comprano un biglietto a testa. Gli ingegneri invece ne comprano uno per tutti. Quando sul treno arriva il controllore gli ingegneri corrono a chiudersi in bagno. Il controllore, esaminati i biglietti dei matematici, bussa alla porta del bagno. Dall’interno un ingegnere risponde:
- Occupato!
E il controllore:
- Biglietti, prego.
Da sotto la porta, gli ingegneri mostrano il loro unico biglietto, il controllore lo vidima e glielo restituisce. Al ritorno a Pisa i matematici, vista la scena dell’andata, comprano un solo biglietto per tutti. Gli ingegneri, invece, nessuno. All’arrivo del controllore i matematici corrono nel bagno e gli ingegneri (tutti tranne uno) in un altro bagno. L’ingegnere rimasto fuori bussa alla porta del bagno dei matematici. Uno dei matematici risponde:
- Occupato!
E l’ingegnere:
- Biglietto, prego…
Varie info
Articolo pubblicato giovedì 13 dicembre 2007 alle 02:15
Segnala questo articolo.. e sentiti utile!
6 Commenti »
Puoi lasciare un tuo commento, oppure fare un trackback dal tuo sito.
Lascia il tuo commento
1
Andrea Carapezzi - Pubblicato il 13 12 2007 alle 10:58
Uno dei sette problemi del millenio, la congettura di Poincaré, è stato risolto da un russo: tale Grigory Perelman. Questo personaggio da film però non ha mai ritirato il premio e ha snobbato la medaglia Fields(corrispettivo Nobel per i matematici).
http://it.wikipedia.org/wiki/Grigori_Perelman
Vi consiglio vivamente di leggere la sua storia.
Ciao Dade!
2
Davide - Pubblicato il 13 12 2007 alle 14:09
Ciao Andre,
avevo letto la notizia.. Tipetto tranquillo questo.
L’unica cosa che proprio mi sfugge: a che serve sta benedetta congettura di Poincarè?
“L’enunciato di Poincaré tenta di dimostrare che la sfera è il più semplice campo in cui un qualsiasi cammino chiuso possa essere contratto fino a diventare un punto (Ogni varietà chiusa n dimensionale omotopicamente equivalente alla n-sfera è omeomorfa alla n-sfera).”
Ok. Quindi?
3
maria - Pubblicato il 14 12 2007 alle 13:59
sto trattenendo le risate……
4
Davide - Pubblicato il 14 12 2007 alle 14:59
Simpatica! :P
5
zivvo - Pubblicato il 17 12 2007 alle 21:23
http://www.claymath.org/
se volete un gossip perelman è in islanda a pescare i tonni e manda un caloroso vaffanc a tutti quanti, non scherzo..
6
Davide - Pubblicato il 21 12 2007 alle 01:32
Ammirevole! Sono i tonni che danno soddisfazioni! ;)