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.

Vuoi essere il primo a lasciare un commento per questo articolo? Utilizza il modulo sotto..

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