Come programmatore sono sempre stato affascinato dagli algoritmi, specialmente se compatti ed eleganti<\/p>\n
Ci sono, per\u00f2, dei problemi per la cui soluzione non esistono algoritmi efficienti; di contro, per gli stessi problemi, se viene presentata una soluzione, questa \u00e8 immediatamente e facilmente verificabile come corretta. Prendete, per esempio, una mappa con un sacco di isole e ponti: non esiste un algoritmo efficiente che tracci un percorso per visitare tutte le isole una sola volta, ma se vi viene presentata una soluzione, \u00e8 facile capire se sia corretta. Un altro problema da un lato pi\u00f9 teorico, ma con tremende ripercussioni pratiche \u00e8, dato un numero, capire se sia il prodotto di due numeri primi e di quali. Se quest’ultimo problema \u00e8 semplice con numeri piccoli, non lo \u00e8, fortunatamente, per numeri molto grossi. Perch\u00e9 \u00abfortunatamente\u00bb? Perch\u00e9 la gran parte di transazioni informatiche crittografate si basa su questo assunto. Se leggete che qualcuno ha trovato un algoritmo per fattorizzare rapidamente numeri di grandi dimensioni, iniziate a preoccuparvi davvero.<\/p>\n
Charles Stross<\/a>, uno dei miei autori di fantascienza preferiti, ha addirittura ipotizzato che la soluzione per via algoritmica di problemi NP-completi porterebbe rapidamente alla creazione di una singolarit\u00e0 tecnologica<\/a> con conseguente fine della nostra civilt\u00e0. Robot 52<\/a> ha pubblicato il gustosissimo raccorto Anticorpi<\/em> ambientato nell’universo della Lavanderia in cui Stross analizza, appunto, questa eventualit\u00e0.<\/p>\n Per ora non \u00e8 nemmeno stato dimostrato se esistano soluzioni algoritmiche ai problemi NP-completi. Secondo un articolo di Scott Aaronson<\/a> pubblicato sull’ultimo numero di Le Scienze<\/em><\/a> (a cui vi rimando per una trattazione pi\u00f9 autorevole di questa), anche con i computer quantici non sarebbe possibile risolvere ogni tipo di problema, in particolar modo quelli NP-completi, per un mero fatto di leggi fisiche.<\/p>\n Meglio: di leggi fisiche attuali, perch\u00e9 sarebbe possibile realizzare un computer in grado di risolvere ogni tipo di problema (anche quelli ancora pi\u00f9 complessi dei problemi NP-completi) usando leggi della fisica in contrasto con quelle attuali. Mi ha divertito abbastanza il concetto di computer che si basa sulle curve temporali chiuse (il nome scientifico dei viaggi arbitrari nel tempo): si tratta in pratica di un computer che risolve un problema in un tempo lungo a piacere che comunichi, per\u00f2, la soluzione appena dopo che gli \u00e8 stata sottoposta.<\/p>\n Forse un computer del genere non verr\u00e0 mai realizzato, ma se lo fosse mi eviterebbe, finalmente, di sentire lamentele sulla lentezza di Windows. Il vantaggio sarebbe anche che la fine dell’Universo verrebbe prorogata indefinitivamente a causa del tempo necessario per far girare Windows.<\/p>\n","protected":false},"excerpt":{"rendered":" Come programmatore sono sempre stato affascinato dagli algoritmi, specialmente se compatti ed eleganti Ci sono, per\u00f2, dei problemi per la cui soluzione non esistono algoritmi efficienti; di contro, per gli stessi problemi, se viene presentata una soluzione, questa \u00e8 immediatamente e facilmente verificabile come corretta. Prendete, per esempio, una mappa con un sacco di isole […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"activitypub_content_warning":"","activitypub_content_visibility":"local","activitypub_max_image_attachments":3,"footnotes":""},"categories":[6,11,40,20],"tags":[58,142,298,330,455],"class_list":["post-27","post","type-post","status-publish","format-standard","hentry","category-fantascienza","category-informatica","category-matematica-scienza","category-programmazione","tag-algoritmo","tag-computer","tag-matematica-scienza","tag-np-completo","tag-tempo"],"_links":{"self":[{"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/posts\/27","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/comments?post=27"}],"version-history":[{"count":0,"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/posts\/27\/revisions"}],"wp:attachment":[{"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/media?parent=27"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/categories?post=27"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/luigirosa.com\/index.php\/wp-json\/wp\/v2\/tags?post=27"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}