I problemi del millennio, ridendoci sopra..

Pubblicato da Davide, Aggiornato martedì 18 dicembre 2007 6 Commenti »

Questo articolo e' stato scritto piu' di 6 mesi fa.. In teoria non cambia nulla, sed panta rei: se trovi link o informazioni datate segnalalo pure. :)

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…

6 Commenti »

Puoi lasciare un tuo commento, oppure fare un trackback dal tuo sito.

  1. 1

    gravatar

    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. 2

    gravatar

    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. 3

    gravatar

    sto trattenendo le risate……

  4. 4

    gravatar

    Simpatica! :P

  5. 5

    gravatar

    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. 6

    gravatar

    Ammirevole! Sono i tonni che danno soddisfazioni! ;)

Lascia il tuo commento

 

http://livregratis.fr/ - http://club-ebook.fr/

Utilizzando il sito, accetti l'utilizzo dei cookie da parte nostra. maggiori informazioni

Questo sito utilizza i cookie per fonire la migliore esperienza di navigazione possibile. Continuando a utilizzare questo sito senza modificare le impostazioni dei cookie o clicchi su "Accetta" permetti al loro utilizzo.

Chiudi