YATDL

Yet Another To Do List:

• dire davvero almeno qualcosina sulla prospettiva libertarian, come millantato con grande sfacciataggine, nonostante non abbia alcuna idea sul da dove cominciare né su che taglio dare; nel frattempo vi segnalo il nuovo blog di Fabristol: Who is John Galt?. Se ancora non l'avete aggiunto al vostro aggregatore, o addirittura non sapete cosa sono i feed RSS, vi segnalo giusto un paio di post: Sul rapporto tra imprenditoria e stato e Imbrigliare (anche) il web;
• spiegare davvero perché gli aerei volano (che, in fondo, è mooolto più semplice di così);
• fornire la mia versione di una spiegazione "divulgativa" della "filosofia" della rinormalizzazione (dopo quella di ToMaTe);
• mi sono ritrovato a ripensare recentemente alle due circolarità nei principi di Newton: ora che ho un blog potrei "pubblicare" qualche mio appunto del prim'anno dell'università;
• riguardando quegli appunti, ho ritrovato alcune righe sul concetto di probabilità che meriterebbero di essere sviluppate, chissà che non ci scappi un post;
• ho ritrovato pure — che risate! — qualche paginetta sul "Sistema cosmocentrico", o "Teoria endosferica del campo": allora non c'era Internet, o almeno non era così diffusa, o almeno io non vi ero così familiare, e trovare chicche come queste in una biblioteca di facoltà non era la stessa cosa che capitare, oggi, su uno qualsiasi degli innumerevoli siti-web che spiegano come il loro autore ha scoperto la Vera Natura del Mondo: se decido di non vergognarmene troppo potrei anche pubblicarla, giusto per rimuovere qualche ragnatela da questo blog che altrimenti ammuffisce...

Nel frattempo approfitto di questo post per segnalare, off topic, le bellissime slide Against Space di Sean Carroll.

Vuota apologia del libertarianismo

Dicevo che il Libertarianismo è una di quelle "scoperte" che ti cambiano radicalmente il modo di vedere tutte le cose; e vi sarà sembrata, lo so, una di quelle frasi romantiche, di chi ama naufragare fra per sempre e mai piú, e immaginare l'infinito dietro l'ermo colle.

E invece è letteralmente così, ti rivolta davvero tutto il mondo come un calzino: lo shopping, lo stato, la società, l'ecologia, i diritti fondamentali degli uomini, non sono più gli stessi; non è più la stessa cosa votare, pagare le tasse, andare a scuola, al lavoro, (non) fare ricerca scientifica. Persino l'astrologia, l'omeopatia e Vanna Marchi (e ditemi voi se è romanticismo Vanna Marchi!) non sono più quelli di prima!

 

Chiaramente sto parlando della mia esperienza personale: non so se tutti i libertari sono passati attraverso un'analoga fase tellurica o se magari hanno vissuto un'esperienza simile ma in più tenera età e, quindi, con meno sconvolgimento (o, più banalmente, sono stati libertari "da sempre").

 

Personalmente, per quanto riguarda la portata rivoluzionaria, trovo che il paragone naturale sia con la fisica moderna e il Darwinismo: se, da una parte, Relatività e Meccanica quantistica ridefiniscono la stoffa con cui è fatto il mondo (spazio, tempo, oggettività, causalità...), dall'altra il Darwinismo tocca più da vicino proprio l'essere umano (chi siamo, da dove veniamo, dove andiamo). Ebbene, la prospettiva libertaria rappresenta il vertice di questo climax perché sconvolge il concetto di uomo nella società, e dunque te la ritrovi dappertutto, quotidianamente.

Ma, sempre in chiave di portata rivoluzionaria, c'è un aspetto profondamente diverso fra Libertarianismo, da una parte, e Relatività, Meccanica quantistica e Darwinismo dall'altra: mentre queste ultime sono scienze consolidate e mainstream, e il Darwinismo addirittura, pur in facili semplificazioni, è addirittura patrimonio comune (ok, lasciamo stare in questo momento l'Intelligent Design...), il Libertarianismo rappresenta invece una specie di terra ignota, ignobile persino, priva anche del fascino trasgressivo dei tabù.

E' stato del tutto casualmente, infatti, che qualcuno mi ha indicato Rothbard, Friedman e prima ancora la scuola austriaca di economia. Eppure, esattamente come succede con Darwin, l'unica reazione che si prova, a posteriori, è semplicemente un: ma come ho potuto essere stato cieco per tutti questi anni? E, a differenza di Darwin, com'è possibile che tanta gente, colta e istruita, progressista, sia del tutto ignorante rispetto a questo modo così naturale di vedere le cose?

 

Va bene, direte voi, ora piantala di girare attorno alla questione e di creare tutta questa suspense: dicci finalmente cos'è, cosa dice questa teoria libertaria della società (ché a leggere Wikipedia sembrano dei pazzi furiosi).

 

La cosa più semplice che potrei fare, in effetti, è proprio fornire qualche link: oltre a Wikipedia ci sono tante fonti online su argomenti libertari e ci sono anche ottimi blogger che ne parlano.

Il punto è che io stesso ero entrato in contatto con alcuni concetti libertari, pur in maniera casuale e tutt'altro che sistematica, proprio attraverso letture sporadiche da alcuni blogger (ad esempio il lume rinnovato), e tuttavia non ero riuscito a coglierne la portata. Un po' perché ero viziato da tutta una serie di pregiudizi inconsapevoli molto comuni e di cui mi sono dovuto letteralmente liberare con non poca fatica, e un po' perché si trattava di concetti isolati di cui mi mancava il contesto (contesto tanto fondamentale proprio perché il Libertarianismo presuppone un cambiamento di prospettiva radicale rispetto al modo di pensare comune). E infatti, almeno da questo punto di vista, un po' mi sono pentito dei miei post recenti in cui riportavo "beceramente" dei brani di Rothbard, perché ottengono in molti casi lo stesso (controproducente) effetto nel lettore non-libertario: straniamento e sospetto.

Quel che mi piacerebbe, invece, è provare a fornire un percorso, anche solo accennato, sicuramente da approfondire poi altrove, che possa però facilitare la strada ad altri che si trovano in una situazione simile a quella in cui mi trovavo io fino a qualche mese fa. Gran parte dei pochi lettori che mi seguono, infatti, almeno io credo, non sono libertari per lo stesso motivo per cui non lo ero io: semplice e pura ignoranza.

 

A coloro che, per ingannare l'attesa (sicuramente lunga, potenzialmente vana) di una prossima puntata, su questi schermi, su questi temi, volessero comunque cominciare da Wikipedia, chiederei almeno di non affrettare il giudizio: le pagine di Wikipedia, giocoforza, espongono le idee libertarie in maniera concisa, evidenziandone le tesi, manco a dirlo, rivoluzionarie. E proprio in quanto tali, prese così, dall'alto, queste tesi possono apparire al limite dell'irragionevolezza. Di più: a volte possono anche esserlo, irragionevoli, perché nella semplificazione di una voce enciclopedica possono rappresentare il risultato estremo di un approccio del tutto inusuale. Il punto è che — e in questo effettivamente il paragone con la fisica moderna e il Darwinismo non regge decisamente più — il Libertarianismo non è un monolite, accentrato, chessò, sulle tesi di Rothbard o di Friedman (che, tanto per dire, erano spesso in disaccordo reciproco su tante cose). Il Libertarianismo, in tutte le sue varie forme rappresenta una prospettiva sulla società, un modo di pensare e di affrontare questioni in cui semplicemente hai imparato a evitare "i soliti errori". Su molte questioni non esiste la soluzione libertaria (al massimo c'è la soluzione di Rothbard, quella di Friedman, e spesso quelle più "famose" sono le più "estreme", da cui, almeno in parte, l'immagine diffusa di "pazzi furiosi"). L'accordo, se vogliamo, è "in negativo", su quali soluzioni "sicuramente non funzionano" e su quali sono i fattori rilevanti, nella ricerca di una soluzione.

 

Questo, tra l'altro, per dire che no, non ho trovato l'unica verità politica a cui tutti dovrebbero adeguarsi, che sarebbe oltremodo ingenuo. L'effetto di devastante rivoluzione della prospettiva libertaria è in negativo, riguarda la quantità di credenze implicite e apparentemente naturali che improvvisamente si frantumano, si rivelano quali falsi preconcetti che da sempre hanno distorto la visione della società.

Proprio come con la fisica moderna e il Darwinismo, il panorama che ti si para davanti è sterminato, e approfondirlo richiede(rebbe) tempo ed energie, ma ugualmente, da subito, capisci che, qualunque cosa troverai, non sarà come quello a cui eri abituato.

 

Insomma: non è tanto una o più specifiche tesi finali di particolari libertari, quanto la prospettiva, che vorrei provare a farvi scorgere, in qualche modo, in futuro, su questo blog. Non ho idea di come fare, dovrò cercare di ricordare com'ero, io stesso, qualche mese fa (e già mi sembra un io lontanissimo ed estraneo), come ragionavo, cosa mi risultava assolutamente impossibile da concepire, ma soprattutto come invece sono arrivato a concepirlo, prima, e, ben presto, a trovarlo addirittura naturale e ovvio.

ilPost /2

Se c'è una cosa che, sin "da piccolo", odiavo dei giornali, era quel loro entrare a gamba tesa in medias res, ricamando nei minimi dettagli sull'intonazione della voce con cui Tizio rispondeva sibillino al commento con cui Caio faceva seguito all'esternazione di Sempronio... sulla notizia di cui s'era persa ogni traccia... sin dall'inizio.

E allora Dio benedica ilPost, che su molte notizie riempie una nicchia ecologica informativa che è pazzesco pensare che nessuno abbia mai cercato di occupare (e onestamente non saprei dire se la colpa è più da parte dei giornalisti o da parte dei lettori, che forse non hanno nemmeno questa esigenza e la nicchia che ho in mente io, di fatto, forse — in Italia? — non esiste nemmeno...).

Com'è, come non è, fatto sta che ilPost risponde in maniera estremamente efficace alla mia esigenza di contestualizzazione e comprensione, e per quelle notizie che tornano alla ribalta come seguito di fatti ormai remoti, o per quelle notizie che sin dall'inizio nascono confuse e frammentate, o per quelle notizie che crescono così smisuratamente in "commentari" da insabbiare i fatti su cui dovrebbero poggiarsi; per notizie, dicevo, che ricadono in una o più o in tutte queste categorie, ilPost mi regala pezzi che suonano rassicuranti anche solo a leggerne il titolo.

Esempi recenti:

• Perché la FIAT non fa lavorare i tre operai di Melfi
• Cosa si sa delle presunte violenze sessuali di Julian Assange
• La storia di Fini e della casa a Montecarlo

Fra P e NP(-completi)

 

Proseguo dal post precedente.

E' venuto fuori un post molto lungo, anche se più breve di quel che avrei voluto...

 

Chiariamo innanzitutto alcuni aspetti del tutto generali sui criteri alla base della classificazione della complessità computazionale di un problema.

 

Efficienza algoritmica come limite superiore alla complessità di un problema

 

La legge di scala (polinomiale, esponenziale, etc) delle risorse computazionali (tempo, memoria, etc) in ragione della taglia del problema (le cifre del numero da fattorizzare, il numero di amminoacidi della proteina da foldare) è, strettamente parlando, una caratteristica dell'algoritmo, non del problema: posso infatti benissimo immaginare di risolvere un problema P con un algoritmo che scala esponenzialmente, basta essere sufficientemente "ingenuo" e "sprecone".

Dato però un algoritmo capace di risolvere un certo problema, posso comunque dire qualcosa sulla complessità computazionale del problema: essa certamente non sarà superiore alla complessità dell'algoritmo. 

Quando dunque voglio parlare di complessità di un problema in termini di risorse, dovrò necessariamente parlare di complessità non maggiore di quella del miglior algoritmo noto: potrà sempre succedere di scoprire un algoritmo più efficiente per un problema, dimostrando così che la sua complessità computazionale era effettivamente più piccola di quella che credevamo (e storicamente è proprio successo così per alcuni problemi che sembravano più "difficili" di quel che erano, uno per tutti il test di primalità, il problema, cioè, di stabilire se un numero è primo o meno — senza dover trovare esplicitamente i suoi fattori primi). 

L'unico modo che avremmo per poter dire che un problema è davvero, intrinsecamente "difficile" sarebbe quello di dimostrare che non è matematicamente possibile trovare un algoritmo più efficiente di una certa complessità, ma questo finora, che io sappia, non è mai accaduto per nessun problema. 

Di conseguenza, dunque, le classi di complessità dei problemi tendono ad essere degli insiemi "concentrici" in cui le classi più "complesse" includono quelle più semplici (e.g. P è un sottoinsieme di NP). In realtà non è sempre necessariamente così per tutte le possibili classificazioni e comunque quasi sempre non abbiamo garanzie che l'inclusione sia propria, che esistano cioè problemi che hanno una qualche complessità minima (e.g. un problema che sia in NP ma non in P — che equivarrebbe appunto a dimostrare che P!=NP). 

 

Esempi semplici 

 

Chiarito il senso generale del concetto di "classe di complessità di un problema", possiamo passare ad alcune classi specifiche: P è la classe di problemi per cui si conosce un algoritmo di soluzione che scala polinomialmente nel tempo, EXP quella dei problemi di cui si conosce un algoritmo di soluzione che scala esponenziale nel tempo; PSPACE è quella dei problemi di cui si conosce un algoritmo di soluzione che scala polinomialmente nell'uso di memoria (space), fosse anche in tempo infinito. Evidentemente, per quanto detto prima, P è un sottoinsieme di EXP. Si può poi dimostrare che PSPACE è un sottoinsieme di EXP e dunque la catena di inclusioni "concentriche" è: EXP ⊇ PSPACE ⊇ P. 

 

NP 

 

Bene, veniamo dunque ai problemi NP. La classe NP è definita in modo un po' diverso (è per questo che dicevo che non tutte le classi sono "concentriche": ad esempio sia NP che coNP includono P, ma entrambe non sono (probabilmente) l'una il sottoinsieme dell'altra — a meno che NP=coNP o addirittura che P=NP, e allora sarebbe P=NP=coNP... Se vi interessa dare uno sguardo "grafico" allo Zoo della complessità potete dare un'occhiata a uno di questi diagrammi delle inclusioni; se vi interessano i dettagli potete perdervi nel Complexity Zoo Qwiki). 

Dicevamo, NP: si può definire la classe NP con una legge di scala degli algoritmi, ma per farlo bisogna cambiare definizione di algoritmo: i problemi NP sono quelli per cui è noto un algoritmo non-deterministico (da cui la N della sigla NP) capace di risolverlo in tempi polinomiali. Gli algoritmi non-deterministici (o equivalentemente le macchine di Turing non-deterministiche) rappresentano un modello computazionale molto utile a livello teorico ma di scarsa rilevanza pratica, dal momento che non è possibile costruirne una realizzazione fisica. Praticamente tutti i moderni computer sono invece delle macchine di Von Neumann che implementano una macchina di Turing universale deterministica, e infatti quando si parla di algoritmi senza ulteriori specificazioni si intendono sempre algoritmi deterministici o per macchine di Turing deterministiche. 

Esiste però una definizione del tutto equivalente, che tira in ballo i soliti algoritmi deterministici: i problemi NP sono quei problemi per cui è noto un algoritmo (deterministico) capace di verificare la soluzione in tempi polinomiali. 

Per la cronaca, i problemi NP stanno fra PSPACE e P, ovvero: EXP ⊇ PSPACE ⊇ NP ⊇ P. 

 

NP-completezza: un limite inferiore alla complessità di un problema? 

 

E i tanto chiacchierati problemi NP-completi? Qui le cose si fanno più intricate... e più affascinanti. In effetti quella dei problemi NP-completi non è nemmeno una classe di complessità in senso proprio del termine (non la troverete, infatti, nel super-mega-complicatissimo-diagramma-di-inclusione). 

Il punto cruciale è che la definizione di problema NP-completo cerca di fare quello che le classi di complessità di cui abbiamo parlato finora non possono fare: rappresentare un limite inferiore alla complessità di un problema. Dico cerca perché, ovviamente, se ci riuscisse veramente avrebbe appunto dimostrato che P≠NP. E tuttavia, pur non riuscendoci, il procedimento escogitato per la definizione di NP-completezza, la riduzione polinomiale, è in grado di gettare nuova luce su tutta teoria della complessità computazionale. 

Abbiamo, dunque, molti problemi NP che ci sembrano difficili. Ma alcuni di essi, come il test di primalità, abbiamo scoperto essere solo apparentemente difficili — nel 1975 si riuscì a dimostrare che il test di primalità era un problema NP, ma ci vollero 27 anni perché fosse "risolto" con un algoritmo polinomiale! 

Come distinguere, dunque, i problemi che sembrano difficili da quelli che lo sono davvero? Distinguerli proprio sulla base della difficoltà è una petizione di principio, significherebbe sapere che sono difficili, ovvero che P≠NP. Quello che fa, invece, la definizione di NP-completezza è trovare una caratteristica comune a quasi tutti i problemi che, ancora oggi, ci paiono difficili, caratteristica che invece non hanno i problemi facili, che stanno in P. Di più: questa caratteristica è tale per cui, se davvero P≠NP, allora i problemi in NP che non stanno in P sono proprio (almeno) i problemi NP-completi. Detto più precisamente, i problemi NP-completi sono certamente "i più difficili" fra i problemi NP (sempre se P≠NP, altrimenti "tutti i problemi NP sono facili come quelli in P"). 

Quel quasi tutti si riferisce al fatto che esistono alcuni problemi NP che ci paiono difficili (cioè di cui non abbiamo ancora trovato un algoritmo polinomiale per risolverli) ma che non siamo riusciti a dimostrare essere NP-completi — e il problema della fattorizzazione dei numeri composti, alla base di quasi tutte le tecniche crittografiche usate comunemente, è proprio uno di questi. Se davvero P≠NP e dunque non tutti i problemi NP sono ugualmente facili, ciascuno di questi problemi potrebbe, più o meno indipendentemente dagli altri:

• essere "semplicemente" un problema P, come il test di primalità, e un giorno, chissà, riusciremo a trovare un algoritmo di soluzione polinomiale;
• essere anch'esso un problema NP-completo, solo che ancora non siamo riusciti a dimostrarlo;
• essere di una complessità computazionale intermedia.

E qui arriva il bello. 

 

Riduzione polinomiale, NP-hard e, finalmente, la definizione di NP-completezza 

 

Ho quasi finito, ma, prima di concludere con la questione della fattorizzazione e delle tecniche crittografiche, direi che è il caso di spiegare in cosa consiste questa mitica NP-completezza, la proprietà di alcuni problemi NP che sembra caratterizzarne la (apparente) difficoltà. 

L'elemento fondamentale è il concetto di riduzione e in particolare di riduzione polinomiale. Ne esistono di due tipi diversi (di Cook e di Karp), ma per amor di brevità sarò impreciso e dirò che ho ridotto il problema A al problema B se, data la soluzione del problema A, so trovare la soluzione al problema B con un algoritmo al più polinomiale. Definisco ora un problema B come NP-hard se un qualsiasi problema NP può essere ridotto polinomialmente a B: se, cioè, con un oracolo capace di darmi istantaneamente la soluzione di B, so risolvere qualsiasi problema NP in tempi polinomiali. Definisco finalmente i problemi NP-completi come quei problemi NP-hard che siano anche problemi NP. 

Come al solito le definizioni sono mere convenzioni e dunque il fatto notevole è che nei primi anni 70 Cook, Karp e Levin mostrarono non tanto che esistono problemi NP-completi quanto che molti problemi concreti erano proprio NP-completi. 

Il fatto che una soluzione "facile" ad uno qualsiasi di questi problemi dischiuderebbe automaticamente le porte a tutti gli altri problemi in NP ne fa chiaramente i rappresentati "più difficili" della classe NP. Non solo: ci dice anche che la "difficoltà" dei problemi NP-completi è essenzialmente la stessa, come se si trattasse di un unico problema sotto diverse sembianze: se uno qualunque di questi problemi ha una soluzione facile, allora tutti quanti ce l'hanno e, di fatto, P=NP; se riuscite a dimostrare che uno qualunque di essi non può avere una soluzione polinomiale, allora nessun'altro potrà averla e, di fatto, avete dimostrato che P≠NP; uno per tutti, tutti per uno.

Per dimostrare, dunque, che un problema NP è NP-completo è sufficiente dimostrare che è riducibile ad uno qualsiasi degli altri problemi di cui è stata già dimostrata la NP-completezza. La scoperta di problemi NP-completi procedette perciò con un effetto valanga: più problemi rientravano nella categoria, più facile diventata ricondurvene di nuovi. Le dimostrazioni di NP-completezza diventarono routine e al momento si contano più di tremila problemi NP-completi.

 

Il problema della fattorizzazione: fra P e NP-completi 

 

Esistono però alcune — poche — notevoli eccezioni: problemi NP, cioè, che (ancora) ci paiono difficili (e dunque sospettiamo non siano P), di cui purtuttavia non si riesce a dimostrare l'NP-completezza. Esempi di problemi di questo tipo sono l'isomorfismo fra grafi, il logaritmo discreto e, udite udite, il problema della fattorizzazione. 

Del resto ci sono ragioni piuttosto profonde per credere che la fattorizzazione non sia un problema NP-completo: per esempio un'istanza di problemi NP-completo può, in generale, avere nessuna, una o centomila soluzioni diverse; la fattorizzazione di un numero composto, invece, è unica. Questa sorta di struttura del problema della fattorizzazione è in effetti sfruttata dal crivello dei campi di numeri, il miglior algoritmo noto di fattorizzazione, che scala più o meno come 2 alla radice cubica di n, qualcosa che qualcuno definisce pur sempre come un andamento sub-esponenziale.

Le possibili relazioni fra P, NP e coNP. Se il problema della fattorizzazione fosse NP-completo, la relazione corretta sarebbe la (b).

Inoltre il problema della fattorizzazione non solo appartiene a NP ma anche coNP, la classe di complessità complementare a NP secondo una precisa definizione che non mi dilungherò a discutere (è già diventato troppo lungo questo post, devo sbrigarmi a chiudere!). Ora, la relazione (insiemistica) fra NP e coNP (ed anche con P) non è nota con certezza matematica, ma ci sono diversi indizi che suggeriscono che NP≠coNP. Ebbene, se la fattorizzazione fosse NP-completa, significherebbe proprio che NP=coNP. Per quel che ne sappiamo, poi, potrebbe pure darsi che l'intersezione fra NP e coNP (a cui certamente appartiene il problema della fattorizzazione) coincida con P stesso (ovvero la fattorizzazione è risolvibile in tempo polinomiale) e purtuttavia P e NP non coincidano! 

Per non parlare, poi, del fatto che per il problema della fattorizzazione, e non per alcun problema NP-completo, siamo riusciti a trovare un algoritmo quantistico, quello di Shor, capace di trovare la soluzione in tempi polinomiali. 

Ma, appunto, non ne parlerò, si è già fatto troppo tardi. 

Sono sicuro che non è rimasto più nessuno, fin qui, a leggere... :-)

La fattorizzazione non è un problema NP-completo (che si sappia)

Questa storia della dimostrazione (ormai quasi definitivamente smontata) che P≠NP sta riportando in superficie il diffusissimo errore secondo cui se P≠NP allora i crittografi e i loro clienti potranno dormire sonni tranquilli (ho citato la mia amica Sylvie, ma è un'affermazione piuttosto frequente).

L'errore consiste nel considerare il problema della fattorizzazione dei numeri composti un problema NP-completo, cosa che non è affatto dimostrata e, anzi, ci sono forti indicazioni che portano a credere che non sia tale: se avete tempo, vi ri-consiglio caldamente tutte le lezioni del corso di Scott Aaronson: Quantum Computing Since Democritus; se avete fretta e vi interessa la questione della "difficoltà" della fattorizzazione, potete limitarvi alla lezione n° 6: P, NP, and Friends.

Che quello della fattorizzazione sia un problema NP-completo è un fraintendimento molto diffuso, io lo scoprii proprio quando mi imbattei nelle lectures di Scott Aaronson: in realtà molto probabilmente si tratta di un problema "più semplice" dei problemi NP-completi, per cui potrebbe benissimo darsi che si scopra che sia un problema "facile" (P) senza che ciò implichi che siano facili anche i problemi NP-completi (molto più probabilmente si tratta di un problema che ricade in un classe intermedia fra P e NP). Detto al contrario: anche se fossimo in grado di dimostrare che i problemi NP-completi sono "davvero" difficili, il problema della fattorizzazione dei numeri composti (e dunque il problema di violare un codice crittografico) potrebbe benissimo rientrare nella categoria dei problemi "facili" (P).

Tant'è che per il problema della fattorizzazione esiste un algoritmo quantistico (il famoso algoritmo di Shor) capace di risolverlo in tempo polinomiale, mentre — nonostante si senta spesso dire il contrario — non è noto alcun algoritmo quantistico capace di risolvere problemi NP-completi in tempo polinomiale, e se mai un giorno si dovesse scoprirne uno, sarebbe sicuramente molto diverso dall'algoritmo di Shor.

Vi siete persi?

Spero di riuscire a buttar giù un "riassuntino" della faccenda quanto prima (cioè: ho già cominciato a scrivere qualcosa, ma sta venendo più lungo di quel che credessi; così ho pensato di uscire subito con questo post giusto per (tentare di) restare "sulla notizia"...).

 

Prima di chiudere, però, vorrei dire due parole sul perché questa questione dell'equivalenza (o meno) delle classi P e NP mi appassiona tanto.

Il fatto è che non si tratta di uno dei problemi da un milione di dollari, o di uno dei più difficili problemi matematici ancora irrisolti, ma si tratta del Problema tout court: se tutti i problemi NP fossero risolvibili polinomialmente, sarebbe possibile programmare un computer per risolvere in poco tempo anche tutti gli altri problemi da un milione di dollari.

C'è addirittura chi crede che l'impossibilità algoritmica di risolvere problemi NP-completi in tempo polinomiale sia consustanziale alla stessa struttura fisica di cui è fatto il mondo.

Come chi?, ma Scott Aaronson, no? :-)

ilPost

Non mi ero abbonato subito ai feed: sono troppi, e già soffro pesantemente di eccesso di informazione.

Però, grazie agli shared item di Aubrey (e alla mia pazienza di non depennarlo, visto che lui stesso shara così tanto da non riuscire a stargli dietro), mi è capitato di leggere molti articoli pubblicati sul Post, e il giudizio è nettamente, estremamente positivo. In realtà, per quanto mi riguarda, poteva benissimo essere un effetto del filtro di Aubrey, ma anche in questo caso bisognerebbe pur ammettere che qualcosa di buono (i. e. che passa il filtro) capita molto spesso.

Il giudizio positivo si riferisce al fatto che, cosa assolutamente straordinaria in Italia, sembra di leggere articoli di un giornale vero: vi si trova, cioè, rilevanza, competenza, un uso estremamente pertinente di una pluralità di fonti (tutte puntualmente citate quando non linkate) e un'estrema obiettività e pacatezza nell'esposizione dei fatti — e con obiettività non mi riferisco ad un acrobatico equilibrismo fra due fazioni opposte, modificabile a piacimento da ambo le parti semplicemente "sparandola più grossa", ma ad una difficilmente definibile pratica di "buon senso" che pareva estinta in Italia.

Intendiamoci, non sto dicendo che non ci siano articoli "d'opinione", né che mi ritrovi pienamente in tutti gli articoli di questo tipo, però, nell'insieme, il risultato è qualcosa che suscita autorevolezza, ovvero quel che dovrebbe essere "il minimo sindacale" perché un giornale possa davvero chiamarsi tale — il "minimo sindacale", perché poi ci sarebbero, ad esempio, le inchieste, come la (ormai non più) recente Top Secret America pubblicata dal The Washington Post (e di cui si può trovare un bel sunto schematico della prima parte — indovinate? — proprio sul Post).

 

PS

Sto resistendo abbastanza, non ho ancora cancellato i feed del Post dal mio gReader, ma non è facile: sono abbonato anche, per quanto riguarda le news, ai feed di RaiNews24 e de La Stampa, ma di quelli leggo solo i titoli, tutti in una volta, e segno come letti in blocco (giusto per avere un'idea di quel che accade nel mondo — e no, quelli di corriere e repubblica sono troppi e inutili persino da leggere per titoli e in blocco...), mentre molto spesso del Post vorrei avere il tempo di leggere e approfondire. Qualcosa riesco a leggere, ma ho il fondato sospetto che sia solo perché il resto della blogosfera, nel bel mezzo di agosto, è quasi tutta in vacanza... :-(

zibaldone

Sono vivo, sono vivo. E non è che non abbia niente da dire...

Qualche commento sparso che mi ero appuntato di passaggio, giusto per rendere la cosa verosimile.

 

• Settimana scorsa sono finalmente passato a Lucid Lynx, ma la vera novità è vecchia già di qualche mese: ho deciso di provare GNOME... e non me ne sono ancora pentito!
  KDE era KDE 3.5. KDE4 è un'altra cosa, ha fatto il pieno di aspettative, tutte puntualmente deluse. Il punto forte di KDE era la completa customizzabilità, e con KDE4 è stata completamente rasa al suolo. Inoltre un sacco di applicazioni ora sono piene di bachi e prive di funzionalità: da konsole alla mitica gwenview, ora diventata amorfa e inutile.
  Ma sto sparando sulla crocerossa, ormai anche pollycoke parla male di KDE4 :-)
  E GNOME? Non è male. KDE 3.5 si rimpiange sempre, ma rispetto a KDE4 in cui sembrava sempre di essere in un ambiente trabalante e contraddittorio GNOME ha quell'aria di desktop uniforme e funzionante che è stato un piacere ritrovare. Finalmente non c'è più quell'eterna sensazione di precarietà, di cose che un giorno — sì, certo, un giorno — saranno fantasmagoriche — ma intanto non funzionano. A parire da Konsole... ehm, da gnome-terminal, che si apre sempre con le stesse dimensioni, e si può persino — ma pensa! — scegliere quali.
  E poi così potrò assaggiare "subito" tutte le novità che Mark Space Cowboy Shuttleworth sta macchinando... o farà, GNOME, la stessa fine di KDE 3.5?

• Per metterci anche un pizzico di attualità, rendo qui omaggio ad Arnold, venuto a mancare settimana scorsa. Non è certo per questo che é diventato famoso, ma a me piace comunque ricordarlo così:

  Mathematics is a part of physics. Physics is an experimental science, a part of natural science. Mathematics is the part of physics where experiments are cheap.

• 
  accessi al sito
  (pochiiiissima ggente)
  Quasi sicuramente nessuno se ne sarà accorto, visto che da queste parti passa pochiiiissima ggente e del tutto per caso (meno male che esistono i feed... ehi, Fabristol, come fai a farne a meno?!?), nessuno se ne sarà accorto, dicevo, ma da un po' di tempo google non permette più il link diretto alle immagini hostate su un googlegroups, il che ha la spiacevole conseguenza che la maggior parte delle mie immagini di corredo ai miei post ora non è più visibile.

  
  meno male che esistono i feed

  Non credo riuscirò a trovare il tempo per spostare tutte le immagini che stanno qui e metterle qui e soprattutto correggere tutti i link e i src in tutti i vecchi post. Magari lo farò per qualcuno dei vecchi post più significativi, ad esempio questo, in onore a Borges oppure il finale della serie sulla visione delle api, in cui le immagini non sono solo accessorie ma sono lo scopo finale di tutto il thread.
  Ma, inutile precisarlo, i tempi saranno i soliti di questo blog.

• Ho letto l'intervista a Eco di AubreyMcFato. Se riesco provo a scriverci un breve post, credo lo intitolerò "Non toccatemi Eco" (ma visti i precedenti, non fatevi troppe aspettative basandovi sul titolo...)

• Invece che uno solo, vorrei tanto scriverne un'intera serie, di post, a tema libertario (il sostantivo è più equivoco, almeno in italiano: libertarianismo? libertarismo?). E' una di quelle "scoperte" che, e non sto esagerando, ti cambiano radicalmente il modo di vedere e concepire praticamente tutte le cose. Vedremo se e cosa riuscirò a comporre... (a proposito, Fabristol, com'è che non hai ancora scritto un post in chiave libertaria su Falcon 9 e Space X?).

non toccatemi Bellone...

...che per me è un mito: mi ha fatto conoscere Quine, ancora piú intoccabile, e la vera storia della fisica, fatta non di aneddoti, experimentum crucis e magnifiche sorti e progressive, ma di vie tortuose, ramificate e percorse anche a ritroso.

Epperò, ha ragione Leucophaea, qui Bellone mi cade davvero!

Sono molto restio ha seguire Leucophaea nel suo parallelo tra antievoluzionismo e anti-AGW, però, al di là delle motivazioni, questo specifico editoriale di Bellone è effettivamente quasi una dimostrazione definitiva della vacuità delle tesi "negazioniste".

Dimostrazione di vacuità perché se leggi critiche piuttosto deboli all'AGW su, chessò, Avvenire, puoi sempre pensare che ci siano ragioni più solide, semplicemente troppo tecniche per Avvenire. Ma se a parlare è nientepopodimenoché Enrico Bellone, che dai suoi libri sei abituato a trovarlo sempre estremamente profondo e denso, e se parla da nientepopodimenoché un editoriale su Le Scienze, e se la prima scomoda verità con cui — lui, in quel contesto — esordisce è che la CO2 non è la regina tossica dell'inquinamento ma un mattone fondamentale della vita... be', insomma, se non fosse Enrico Bellone ti verrebbe quasi da ridere.

E ancora meno da ridere viene a leggere quell'e allora? che riassumerebbe la sua stessa difesa: Ho citato un sito dove si parla della CO2 e mi si rimprovera in quanto esso riprenderebbe un articolo apparso su «l’Avvenire»: e allora?.

Se volete i dettagli, Climalteranti ospita tutto il dibattito: editoriale, critica e controrisposta.

Io ho un mito di meno.

Esclude i pregiudicati dalla processione, spari al prete

Anche contro la mafia la Chiesa ha un potere enorme, se solo si decidesse ad usarlo più spesso e in maniera coordinata dall'alto. A parte rari casi come questo, troppo spesso si lascia tutto alla buona volontà dei singoli. E al loro coraggio, perché, come sottolineava Falcone, l'essere soli è uno dei principali motivi per cui, a toccar la mafia, si muore.

 

PS

D'ora in poi, ancor più di prima, dovrete perdonare il ritardo dei miei commenti, diciamo così, d'attualità, rispetto alle notizie...

Per una nuova libertà /3

Soluzioni libertarie a problemi attuali: conservazione, ecologia, sviluppo — Inquinamento

È interessante notare che ci sono due aree in cui l'inquinamento è diventato un problema grave: l'atmosfera e l'acqua, e in particolare i fiumi. Si tratta però proprio di quelle aree in cui non è ancora concessa la proprietà privata.

I fiumi, e anche gli oceani, sono in linea di massima proprietà dello Stato; la proprietà privata, e comunque la proprietà privata completa, non è mai stata concessa per le acque. In definitiva, quindi, i fiumi appartengono agli Stati. Tuttavia il diritto di proprietà dello Stato non è un vero diritto di proprietà, giacché i funzionari del governo, pur potendo controllare tale risorsa, non possono raccogliere i frutti del suo valore capitale sul mercato: non possono vendere i fiumi o venderne i titoli in borsa. Di conseguenza, non sono economicamente incentivati a preservarne la purezza e il valore. I fiumi, quindi, dal punto di vista economico, sono "proprietà di nessuno"; perciò, i funzionari hanno permesso che i fiumi potessero essere inquinati e rovinati. Chiunque ha potuto scaricare rifiuti nelle acque. Consideriamo ciò che succederebbe se le imprese private potessero possedere laghi e fiumi. Se una compagnia privata fosse proprietaria del lago Eire, ad esempio, chiunque vi scaricasse rifiuti verrebbe processato per aver aggredito la proprietà privata altrui, costretto a risarcire i danni, a cessare immediatamente l'azione aggressiva, e a desistere da simili violazioni future. Dunque, solo il diritto di proprietà privata porrebbe fine all'invasione-inquinamento delle risorse. È solo perché i fiumi non appartengono a nessuno che nessun proprietario insorge per difendere la sua preziosa risorsa dagli attacchi esterni.

Come ha detto il professor Dolan:

Se la General Motors possedesse il fiume Mississipi, stiamo pur certi che verrebbero chieste alte tariffe per gli effluenti alle industrie e alle amministrazioni comunali site lungo le rive, e l'acqua verrebbe mantenuta pulita, tanto da massimizzare i proventi degli appalti concessi alle imprese che volessero acquisire i diritti all'acqua potabile, alla ricreazione e alla pesca commerciale

Daniele Luttazzi @ raiperunanotte

il voto sia contro l'aborto

Non è questione di libertà di opinione e di espressione della Chiesa.

E' questione della stridente ipocrisia di chi non sembra affatto guidato dalle preoccupazioni etiche e sociali che sbandiera, visto che parla (e tace innumerevoli, troppe volte) in una sola direzione, con obiettivi precisi, temporali, squisitamente politici (nella peggior accezione possibile del termine).

tanto per dire

da friendfeed/spinoza

Il vero, grosso problema dell'Italia dei valori è questo. Non il personaggio specifico in sè, ma l'essere, l'IdV, facile approdo di quaglie d'ogni dove, con conseguenze che abbiamo già sperimentato sul campo (vedi alla voce Sergio De Gregorio).

Tutti gli altri problemi, solo l'ultimo dei quali è la parlantina rustica di Di Pietro, passano in secondo piano, stante il panorama politico italiano. Perchè il voto è ovviamente un compromesso e non ti basta citare un problema di una parte politica: devi anche convincermi che è peggio di quel che trovo da qualche altra parte.

 

Non ne capisco molto di politica, sono tremendamente ingenuo, ma il mio pensiero è questo: nonostante tutto, nonostante anche il grosso e serio problema delle quaglie, continuo a pensare che, in questo momento, un voto a Di Pietro sia il segnale giusto. Il PD ha smesso di rappresentare un'alternativa possibile, viste le numerose manifestazioni di voglia di inciucio; votare qualcuna delle altre alternative non si distinguerebbe molto dal non-voto.

E del resto la dimostrazione più chiara che l'IdV rappresenta in questo momento la valorizzazione migliore del proprio voto viene proprio da Berlusconi stesso e dalla suo rapporto chiunque ma non lui con Di Pietro (molto vicino, in realtà, al rapporto che hanno un po' tutti, con Di Pietro...).

Per una nuova libertà /2

Soluzioni libertarie a problemi attuali: conservazione, ecologia, sviluppo

È vero che diverse risorse naturali, nel passato e nel presente, hanno rischiato l'esaurimento. Ma in ogniuno dei casi ciò non era dovuto all'"ingordigia capitalista"; al contrario, la ragione è da ravvisarsi nell'incapacità del governo di acconsentire alla proprietà privata della risorsa — un'incapacità di perseguire abbastanza radicalmente la logica dei diritti della proprietà privata.

Un esempio è quello delle risorse di legname. Nell'America occidentale e in Canada, la maggior parte delle foreste non appartiene a privati ma ai governi federali (o provinciali). Il governo le dà poi in gestione alle compagnie private. La proprietà privata viene concessa solo per l'utilizzo annuale della risorsa, ma non per la foresta, per la risorsa stessa. In tale situazione la compagnia privata non possiede il valore capitale e quindi non deve preoccuparsi dell'esaurimento della risorsa stessa. Non ha alcun incentivo economico a conservare la risorsa, a piantare nuovi alberi, etc. L'unico incentivo è quello di tagliare più alberi possibile, dal momento che non le viene alcun vantaggio economico dalla conservazione del valore capitale della foresta. In Europa, dove la proprietà privata delle foreste è molto più diffusa, ci sono poche lamentele contro la distruzione delle risorse del legno. Infatti laddove è permessa la proprietà privata delle foreste, è nell'interesse del proprietario preservare e ripristinare le riserve di alberi man mano che procede al disboscamento, affinchè si possa evitare l'esaurimento del valore capitale della foresta.

Quindi negli Stati Uniti uno dei maggiori colpevoli è stato il Forest Service del Dipartimento dell'agricolutra, il quale possiede foreste e concede permessi annuali in base ai quali è possibile far legna, e di conseguenza distruggere gli alberi. Al contrario le foreste private possedute da grandi imprese di legname come la Georigia-Pacific e la U.S. Plywood tagliano gli alberi e rimboscano con metodi scientifici, così da assicurare una riserva futura.

Un'altra conseguenza negativa dell'incapacità del governo americano di permettere la proprietà privata delle risorse fu la distruzione, nel XIX secolo, delle praterie dell'America occidentale. Ad ogni spettatore di western sono familiari il ritratto mistico delle "praterie aperte" e gli scontri spesso violenti fra gli allevgatori di bestiame e gli agricoltori per appezzamenti di terreno. La "prateria aperta" rappresentava l'incapacità del governo di applicare la politica dello homesteading al mutamento delle condizioni del clima secco a ovest del Mississipi. Nell'East, i 160 acri di terreno concessi gratuitamente agli agricoltori che per primi avevano disboscato le terre governative costituiscono un'unità tecnologica funzionale all'agricoltura in un'area piovosa. Ma nelle zone aride dell'Ovest, nessuna fattoria per l'allevamento di bestiame poetva essere organizzata con successo su soli 160 acri di terreno. Il governo federale tuttavia si rifiutò di espandere l'unità di 160 acri e di autorizzare lo homesteading di fattorie più estese. Di qui, la "prateria aperta", sulla quale i proprietari di bestiame potevano muoversi incontrollati su terreni da pascolo di proprietà del governo. Ciò significava però che i pascoli, la terra stessa, non appartenevano a nessuno; era quindi economicamente vantaggioso per ogni allevatore portare il proprio bestiame a pascolare lì e utilizzare l'erba prima possibile, altrimenti sarebbe stata sfruttata da qualche altro allevatore. Il risultato di questo tragico rifiuto di autorizzare la proprietà privata della terra fu un eccessivo utilizzo dei pascoli, la rovina delle praterie a causa del pascolo prematuro e fuori stagione, e l'impossibilità che qualcuno piantasse nuova erba — chiunque si prendeva il disturbo di farlo doveva poi assistere impotente mentre un altro allevatore vi portava a pascolare il proprio bestiame. Di qui i tentativi illegali di molti agricoltori di recintare i terreni appropriandosene — e di qui anche gli scontri delle praterie. [...]

Vi è un settore importante in cui l'assenza della proprietà privata ha causato, e sta ancora causando, non solo l'esaurimento delle risorse, ma anche l'assoluta impossibilità di sviluppare vaste risorse poetnziali. Si tratta dell'enorme e assai produttiva risorsa degli oceani. Gli oceani fanno parte di un demanio internazionale: nessun individuo, nessuna compagnia e nessuno Stato può vantare diritti di proprietà su parti degli oceani. Di conseguenza, essi sono rimasti allo stato primitivo come lo era la terra prima dello sviluppo dell'agricoltura. L'uomo primitivo produceva attraverso le attività di "caccia e raccolta"; cacciava animali selvatici e raccoglieva frutta, noci, frutti di bosco, semi, verdure. Lavorava passivamente all'interno del proprio ambiente, invece di adoperarsi per trasformarlo; dunque egli traeva il proprio sostentamento dalla terra senza tentare di modificarla. Di conseguenza, i terreni erano improduttivi, e solo pochi uomini delle tribù riuscivano a sopravvivere. Solo con lo sviluppo dell'agricoltura, con la lavorazione e la trasformazione della terra attraverso la coltivazione fu possibile l'aumento della produttività e della qualità della vita. E fu solo con l'avvento dell'agricoltura che poté avere inizio la civiltà. Tuttavia, per permettere lo sviluppo dell'agricoltura dovettero essere riconosciuti i diritti di proprietà privata, dapprima sui campi e sulle piantagioni, e successivamente sulla terra stessa.

Per quanto riguarda l'oceano, però, ci troviamo ancora allo stadio primitivo della caccia e della raccolta. Chiunque può catturare i pesci nell'oceano, o estrarre da esso le sue risorse, ma solamente in modo casuale, da semplice cacciatore o raccoglitore. Nessuno può coltivare l'oceano, nessuno può dedicarsi all'acquacoltura. Così veniamo privati della possibilità di utilizzare le immense risorse di pesce e di minerali presenti nei mari. Ad esempio, se qualcuno tentasse di coltivare il mare e di incrementare la produttività delle zone di pesca usando fertilizzanti, questi verrebbe immediatamente privato dei frutti dei suoi sforzi, dal momento che non potrebbe impedire agli altri pescatori di impossessarsi del pesce. Di conseguenza nessuno cerca di fertilizzare gli oceani come avviene invece per la terra. Inoltre, ci sono pochissimi incentivi economici — vi sono anzi dei disincentivi — per chi volesse impegnarsi nella ricerca tecnologica dei modi e mezzi con cui migliorare la produttività delle zone di pesca, o estrarre minerali dagli oceani. Vi saranno incentivi simili solo se verranno concessi i diritti di proprietà di parti di oceani, come avviene per la terra. Già adesso è disponibile una tecnica efficace e semplice per migliorare la produttività dell'industria della pesca [...].

Gli Stati nazionali hanno tentato invano di risolvere il problema della scarsità del pesce con restrizioni assurde e dispendiose delle dimensioni delle reti, della durata delle stagioni di pesca. Nel caso del salmone, del tonno e dell'halibut i metodi di pesca sono rimasti primitivi e improduttivi a causa della limitazione dei periodi di pesca e delle stimolo alla sovrapproduzione in quei periodi. È ovvio che tali restrizioni non fanno assolutamente nulla per stimoplare lo sviluppo dell'acquacoltura. Come hanno detto i professori North e Miller: «[...] Non è nell'interesse di alcun pescatore preoccuparsi del mantenimento dei banchi di salmone. Anzi, è il contrario: è nel suo interesse pescare la maggior quantità di pesci possibile durante la stagione.» North e Miller hanno dimostrato che i diritti di proprietà privata dell'oceano, grazie ai quali i proprietari potrebbe usare tecnologie meno costose e più efficienti e al contempo preservare e rendere più produttiva la risorsa stessa, sono oggi più assegnabili che mai [...].