Illazioni sul rapporto fra i sessi.

 

Spoiler prima di lasciarvi continuare a leggere inutilmente: il titolo è mero clickbait, il rapporto di cui parlerò è semplicemente quello numerico.

 

Scott Aaronson è sempre fonte di mille spunti interessanti di riflessione.

Anche quando sembra cadere su delle banalità da WTF.

Non fa eccezione questa recensione del libro di Max Tegmark [1], in cui però a un certo punto il nostro mette sullo stesso piano di impressiveness le "predizioni" della Relativà Generale (la precessione di Mercurio) o dell'equazione di Dirac (l'esistenza dell'animateria) con quella "di Darwin" sul rapporto numerico fra i due sessi nelle popolazioni delle varie specie animali.

 

Ora, la questione è la solita: l'insopprimibile e sacrosanto desiderio di avere un criterio di demarcazione, ed in particolare di averne uno semplice. Ahimè l'obiettivo, Quine insegna, è semplicemente irraggiungibile, soprattutto in termini di semplicità.

Ma — certo, certo — sono rassegnato alla marginalità della lezione quineiana nel panorama epistemologico corrente, per cui non mi stupisco più di tanto del fatto che Aaronson proponga la sua personale linea di demarcazione: "connecting elegant math to actual facts of experience".

Quel che mi sorprende è che abbia tentato di farci rientrare la teoria di Darwin, in questo connettere matematica elegante a fatti sperimentali, tramite la questione del rapporto numerico fra i sessi.

 

Il fatto è che la questione del sex ratio in chiave evoluzionistica non rappresenta nulla di neanche lontanamente simile ad un experimentum crucis per la teoria di Darwin.

Innanzitutto la definizione stessa del concetto di rapporto numerico fra i sessi è articolata (ne esistono almeno 4 tipologie diverse); inoltre, sì, si possono trovare dei riferimenti alla questione in scritti originali di Darwin (su questa cosa ci torno in chiusura di post, capirete perché scrivevo "di Darwin" fra virgolette), ma i nomi che più si legano alla questione sono quelli, ben successivi a Darwin, di Ronald Fisher e di W. D. Hamilton, e il tema restò a lungo oggetto di discussioni, analisi e ricerche. Anche dal punto di vista meramente sperimentale, infatti, esistono diverse notevoli eccezioni, molte specie in cui, per ragioni anche diverse, i rapporti numerici fra i sessi si assestano su valori significativamente diversi da quello paritario, in modo transitorio o permanente (specie partenogeniche, oppure con pratiche di accoppiamento diversificate come gli afidi, oppure specie eusociali...).

 

Insomma, nessuno, ed io men che meno, nega l'impressiveness della teoria di Darwin; ma mi sembra davvero difficile, in generale, ricondurla ad una singola questione centrale direttamente collegata ad un dato sperimentalmente; e in particolare mi sembra davvero difficile ricondurla a questa cosa del rapporto numerico fra i sessi di una popolazione, soprattutto alla luce della lezione gouldiana del pollice del panda [2].

 

Come dunque può essergli venuto in mente, ad Aaronson, di annoverare la questione della della sex ratio come emblema della forza sperimentale della teoria di Darwin?

Girovagando in rete sull'argomento, pian piano vado formulando un'ipotesi.

Diciamo pure un'illazione: che anche lui abbia cercato in rete, qualcosa come "main evidence for evolution" o "most important claims of evolution" e abbia trovato le "solite" prove (i reperti fossili, l'anatomia e lo sviluppo embrionale comparati come indicazioni di un antenato comune, la resistenza batterica agli antibiotici, etc, etc...); tra l'altro se avesse cercato qualcosa come "evidence for darwin's evolution" si sarebbe imbattuto addirittura in un prodromo del pollice del panda dello stesso Darwin [3]. Finché, questa è la mia illazione, non ha cercato qualcosa come celebrated argument evolution, e si è ritrovato davanti proprio al principio di Fisher, definito appunto "probably the most celebrated argument in evolutionary biology". Senonché a definirlo così fu, be', A. W. F. Edwards, allievo di quello stesso Fisher del cui principio stava tessendo le lodi — pare che venisse proprio chiamato "Fisher's Edwards".

Sia chiaro, tutto vorrei tranne che sminuire Edwards, il quale non era affatto un allievo sfigato e banale adulatore di Fisher: diventò famoso e rinomato genetista, pioniere insieme a Cavalli-Sforza nell'applicazione delle tecniche statistiche alla ricostruzione degli alberi evolutivi; nonché autore della famosa critica all'articolo di Lewontin sulla divisione dell'umanità in razze.

E del resto anche il suo giudizio sull'importanza del principio di Fisher, lungi da me negarlo, è ben fondato: si trattava di un argomento che mostrava come la selezione naturale, anche agendo a livello di singolo individuo, potesse plasmare una caratteristica di popolazione come il rapporto numerico fra i sessi, che invece sembra ovviamente candidata ad essere controllata da una selezione di gruppo; mostrava che a volte era necessario prendere in considerazione, in un modello evoluzionistico, più di due sole generazioni; si è rivelato essere un esempio ante litteram di quelle che verranno poi chiamate "strategie evolutivamente stabili" (ESS) e che portarono all'applicazione in campo genetico delle tecniche di teoria dei giochi; ha avviato i successivi interessi verso le implicazioni evoluzioniste degli investimenti parentali; etc, etc...

Insomma, si tratta certamente di un'idea estremamente feconda, anche se — ed è questo il mio punto — non propriamente "folgorante" e sperimentalmente "eclatante", come vorrebbe il nostro Aaronson.

Tant'è che, ho scoperto, l'idea di Fisher l'ebbe lo stesso Darwin, che la descrisse nella prima edizione del suo "L'origine dell'uomo", ma che rimosse nella seconda edizione proprio perché, e lo scrisse esplicitamente, si rese conto che la questione era in realtà molto più spinosa di quanto avesse inizialmente pensato.

 

 

 

---

[1] Il tema del libro di Tegmark è la sua "Mathematical Universe Hypothesis": sembra di essere sul pezzo delle ultime dichiarazioni di Musk sull'universo come simulazione, ma in realtà questo di Aaronson è un vecchio post di più di due anni fa: ci sono arrivato perché sto leggendo il suo (di Aaronson) ultimo (be', nel frattempo è diventato penultimo) post, in cui ripropone in forma scritta (Dio lo benedica!) il suo intervento, in risposta a quello di Penrose, ad un simposio che sarebbe sui fondamenti della fisica, ma in cui in realtà, almeno nel suo intervento e in quello di Penrose, si parla della coscienza. Anche lì mille spunti interessanti di riflessione, ma non ho ancora finito di leggerlo...

 

[2] L'idea che una progettazione improvvisata alla bell'e meglio (come il pollice del panda, che appunto pollice non è, ma un'estensione del sesamoide laterale) sia un argomento di gran lunga più efficace, per il darwinismo, rispetto ad un adattamento perfetto.

 

[3] Le ipotesi di Darwin, nella prima edizione de L'Origine delle specie, sull'origine delle balene, del tutto simile, nello spirito, all'idea del pollice del panda; poi rimossa dalle edizioni successive per via dell'eccessiva derisione che ne ricevette.

 

Srinivasa Ramanujan

L'uomo che vide l'infinito.

Mi era capitato di leggere il commento di Peter "Not Even Wrong" Woit su The Man Who Knew Infinity il film sulla storia di Srinivasa Ramanujan, famoso bambino prodigio e matematico indiano di inizio '900, e del matematico di Cambridge G. H. Hardy.

Vidi a suo tempo il film su John Nash, "A Beautiful Mind" (e non mi piacque) e lessi — è tantissimo che non vado al cinema! — qualche recensione non propriamente positiva del film su Alan Turing, "The Imitation Game" (qui quella di, tanto per cambiare, P. Woit), per cui mi colpì leggere un parere positivo a proposito di quest'ultimo film su un matematico.

Ebbene, poco fa anche Scott "Shtetl-Optimized" Aaronson ha scritto una sua recensione del film, molto lunga e dettagliata, giudicandolo "eccellente": "Largely just men doing sums": My review of the excellent Ramanujan film.

 

 

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? :-)

darwinisti teorici e darwinisti sperimentali

Il punto c di questo commento di sagredo su Progetto Galileo mi ha fatto ricordare che avevo un post nel cassetto. Finisco ora di scriverlo e lo pubblico subito.

 

C'era una volta (ennesima dimostrazione della tempestività con cui questo blog scatta sulla notizia) Scott Aaronson che annunciò la pubblicazione dell'ultima lezione del corso Quantum Computing Since Democritus. Ho avuto modo di parlare molto di questo corso, anche se meno di quel che mi sarebbe piaciuto. Avrei in tasca, per esempio, almeno un altro spunto che, periodicamente, prende a frullarmi per la testa, ma ormai sta cominciando a formarsi la muffa su quel Bonus Addendum nascosto in fondo alla terza lezione... chissà quando troverò il tempo di tornarci su (anzi, sto cominciando anche a scordarmi tutte le cose che volevo dire a riguardo...).

Nel frattempo, mi limito a sengalarvi quest'ultima lezione, anche perchè non si parla solo di complessità computazionale. Come sempre, del resto, nelle sue lezioni. Ma in questa in particolare, visto che si intitola Ask Me Anything. Anzi, mi permetto addirittura di riportarne, traducendoli molto liberamente (e rozzamente) in italiano, alcuni stralci più significativi e meno tecnici.

...continua

   —   ∴   —   

Scott: Altre domande? Magari una meno tecnica?

D: Come risponderesti ad un sostenitore dell'Intelligent Design? Senza farti sparare?

Scott: Be', davvero non saprei. E' uno di quei casi in cui potremmo applicare il principio antropico: se su questa cosa fosse stato possibile convincerlo con l'evidenza, non si sarebbe già convinto? Secondo me dobbiamo accettare che ci sono persone per cui la cosa più importante nelle proprie convinzioni non è se queste corrispondono al vero; altre proprietà sono più importanti, quali ad esempio il proprio ruolo in una comunità. Stanno giocando, cioè, un gioco diverso, in cui le credenze sono giudicate con standard diversi. E' come un giocatore di basket su un campo di calcio. Come potrà mai vincere?

[...]

Scott: E' chiaro che la religione svolge una qualche funzione, per le persone, altrimenti non sarebbe stata così onnipresente per migliaia di anni o non avrebbe resistito a significativi sforzi per eliminarla. Per esempio, forse le persone che credono che Dio stia dalla loro parte sono più coraggiose in battaglia. O forse la religione è uno dei fattori (fra altri più ovvi) che induce uomini e donne a sposarsi ed avere un sacco di bambini, e dunque rappresenta un tratto adattivo da un punto di vista darwiniano. Anni fa rimasi colpito da un fatto ironico: nell'America contemporanea abbiamo questo stereotipo di elite che crede nel darwinismo e vive spesso da solitario trentenne o quarantenne, e poi abbiamo lo stereotipo di quelli che rifiutano il darwinismo ma si sposano giovani e hanno 7 figli, 49 nipoti e 343 bisnipoti. A questo punto non è una gara fra darwinisti e anti-darwinisti; è una gara fra darwinisti teorici e darwinisti sperimentali!

Se quest'idea è corretta anche solo in parte — che le religioni sopravvivono perchè aiutano le persone a vincere le guerre, ad avere più bambini, etc — allora la domanda che si pone è: come sarai mai in grado anche solo di affrontarli se non diventando anche tu una religione alternativa?

D: Oh, sì, sono sicuro che questo è proprio quel che la gente pensa quando deve decidere se credere o meno in una religione.

Scott: Non sto dicendo che è qualcosa di consapevole, o che le persone la pensano proprio in questi termini. Certamente qualcuno lo fa, ma il punto è che non devono farlo, perchè il loro comportamento sia comunque descrivibile in questi termini.

D: Possiamo anche avere molti bambini senza accettare una religione, se vogliamo.

Scott: Certo, possiamo, ma lo facciamo, in media? Non ho numeri a portata di mano, ma credo che esistano studi che supportano il fatto che le persone religiose hanno in media più figli.

Ora, c'è un altro fattore chiave, ed è che alcune volte l'irrazionalità può essere la scelta più razionale, perchè è l'unico modo di dimostrare a qualcun altro che sei convinto di qualcosa. Tipo, se qualcuno si presenta alla tua porta chiedendoti cento dollari, è molto più probabile che tu glieli dia se ha gli occhi iniettati di sangue e un'aria davvero irrazionale — non hai idea di cosa starà per fare! L'unico modo di rendere efficace una strategia simile è fare in modo che l'apparenza di irrazionalità sia convincente. Il tizio non potrebbe semplicemente fingere, altrimenti lo capiresti. Deve essere molto, molto irrazionale e mostrarsi capace di vendicarsi di te a qualsiasi costo. Se credi che il tizio difenderà il suo onore fino alla morte, probabilmente non vorrai avere a che fare con lui.

Quindi la teoria è che la religione è un modo per convincere se stessi. Uno può dire di credere in un certo codice morale, ma gli altri possono capire che sta mentendo e non fidarsi di lui. D'altra parte, se uno ha una barba molto lunga e prega tutti i giorni e sembra davvero credere che l'aspetterà un inferno eterno se infrangerà i suoi precetti, sta costruendo il suo stesso convincimento. Secondo questa teoria la religione funzionerebbe come un modo di pubblicizzare una convinzione su un certo insieme di regole. Naturalmente le regole possono essere buone o possono essere terribili. Nondimeno, questa specie di convincimento pubblico ad obbedire a un insieme di regole, condite con ricompense e punizioni sovrannaturali, sembra essere un elemento importante di come le società si sono organizzate per migliaia di anni. E' il motivo con cui i potenti hanno convinto i propri sudditi a non ribellarsi, gli uomini hanno convinto le proprie mogli ad essere fedeli e le mogli convinto i propri mariti a non abbandonarle, eccetera.

Insomma, mi sembra che questi siano i tipi di forze "di teoria dei giochi" che Dawkins e Hitchens e gli altri crociati anti-religioni devono affrontare e che forse non riconoscono sufficientemente nei loro scritti. Ciò che gli rende le cose facili, naturalmente, è che i loro oppositori non possono semplicemente saltar fuori e dire "sì, naturalmente sono tutte sciocchezze, ma servono per queste importanti funzioni sociali!" Invece i difensori delle religioni spesso ricorrono ad argomenti che si demoliscono facilmente (almeno dopo Hume e Darwin) perchè la loro vera condizione, sebbene considerevolmente più forte, è di quelle che è molto difficile da sostenere apertamente!

Riassumendo, magari è vero che gli uomini (se sopravviveremo abbastanza a lungo) potrebbero arrivare a ripudiare le religioni, ora che abbiamo qualcosa di meglio con cui sostituire il loro potere esplicativo. Ma prima che ciò accada, credo che avremo bisogno almeno di capire meglio le funzioni sociali che la religione ha giocato per la maggior parte della storia e ancora gioca nella maggior parte del mondo, e forse avremo bisogno di trovare meccanismi sociali alternativi per risolvere lo stesso tipo di problemi.

D: Stavo pensando se ci fosse un altro caso in cui l'irrazionalità sia preferibile alla razionalità.

Scott: Da dove iniziare?

D: Specialmente se hai un'informazione incompleta. Come se avessi un politico che è ben convinto e che non cambierebbe mai i suoi ideali: saresti molto più sicuro che farà quel che dice di voler fare.

Scott: Perchè ha convinzioni. Crede in quel che dice. Per la maggior parte dei votanti, questo conta molto più che l'effettivo contenuto delle convinzioni. Bush da un'impressione molto buona di convinzione.

D: Ma non sono sicuro che ciò sia il meglio per gli interessi degli Stati Uniti.

Scott: Esatto, questo è il punto! Come combatti persone che sono diventati maestri nel meccanismo dell'irrazionalità razionale? Dicendo "no, guarda qui, i tuoi fatti si sono rivelati sbagliati"? A che gioco stai giocando? Prendi un altro esempio: un single al bar. Quelli che hanno più successo sono quelli più abili a convincere se stessi (almeno temporaneamente) di certe falsità: "Sono il più figo qui". Questo è un chiaro caso in cui l'irrazionalità sembra razionale, in un certo senso.

Quantum Computing Since Democritus

Prosegue la pubblicazione delle lectures del corso di Aaronson del 2006. Dopo lo sprazzo isolato di febbraio, in questo giugno ben tre post hanno annunciato tre nuove puntate del corso.

Ovviamente non ho ancora trovato il tempo di leggerle tutte, ma già la prima, How Big Are Quantum States?, offre spunti molto interessanti. Aaronson, lo sappiamo, ama le frasi ad effetto, ed anche ora parte alto:

"computer science" is a bit of a misnomer; maybe it should be called "quantitative epistemology".

Ma questa volta sembra abbastanza convincente.

E' quasi un secolo, ormai, che la meccanica quantistica continua a reggere contro tutti i tentativi di attacco sperimentale, mentre il fastidio "filosofico" che si prova a maneggiarla non si è ridotto punto. Ebbene, leggendo Aaronson si ha davvero la sensazione che i metodi della computer science possano finalmente offrire possibilità concrete per aprire una breccia proprio sul lato concettuale dei problemi. Ma è solo un paradosso, non c'è contraddizione: da una parte davvero la teoria della computabilità guarda alla meccanica quantistica da un punto di vista squisitamente teorico, e tuttavia, ugualmente, lo spirito è innegabilmente galileiano, quello con cui si parte da casi concreti e problemi circoscritti, per lasciar comporre alle loro risposte, le risposte alle domande più generali sui massimi sistemi:

Now that we have quantum computing, can we bring the intellectual arsenal of computational complexity theory to bear on this sort of question? I hate to disappoint you, but we can't resolve this debate using computational complexity. It's not well-defined enough. Although we can't declare one of these views to be the ultimate victor, what we can do is to put them into various "staged battles" with each other and see which one comes out the winner. To me, this is sort of the motivation for studying all sorts of questions about quantum proofs, advice, and communication.

Buona lettura!

genetic algorithms

Biology employs what computer scientists know as genetic algorithms. Sometimes biology simply mutates the candidate solutions, but other times it combines them (which we call sexual reproduction).

Biology has adopted the sexual reproduction technique so widely that it must have something going for it, even if we don’t yet fully understand what it is. In experiments, local search algorithms that employ only mutations (i.e. “asexual reproduction”) consistently do better at solving NP-complete problems than do algorithms that incorporate sex.

The best theory people currently have as to why nature relies so heavily on sex is that nature isn’t trying to solve a fixed problem; the constraints are always changing. For example, the features that were ideal for an organism living in the dinosaur age are different from the features that are ideal for modern-day organisms. This is still very much an open issue.

Scott Aaronson,
Great Ideas in Theoretical Computer Science,
Lecture 11: NP-Completeness in Practice

Shtetl-Optimized

Finalmente!

Dopo tanto tempo Scott Aaronson si è deciso a proseguire con la pubblicazione delle lectures del suo Quantum Computing Since Democritus: è da poco online la lezione numero 12.

Di più, ora inizia un nuovo corso, Great Ideas in Theoretical Computer Science, di cui è già disponibile la prima lezione.

Altre letture per i miei lunghi viaggi in treno! :)

Probabilità negative 2: dalla probabilità ad uno spazio lineare (e poi daccapo)

Riprendo il discorso da dove l'avevo lasciato, qui, sulla lezione 9 di Aaronson.

...continua

   —   ∴   —   

Il percorso ingannevole parte con la rimozione della condizione di normalizzazione per una distribuzione di probabilità. Poiche' tale condizione si traduce semplicemente in un riscalamento complessivo di tutte le probabilità con un fattore costante globale, univocamente determinato dalla distribuzione stessa, si puo' sempre pensare di procedere senza questo vincolo e riapplicarlo solo alla fine quando bisogna confrontare le probabilità con le effettive frequenze misurate sperimentalmente. Del resto il concetto di probabilità nasce proprio come frequenze normalizzate, le frequenze essendo semplicemente non-negative.
 

Se si procede a questa sorta di semplificazione o di generalizzazione del concetto di probabilità, una distribuzione di probabilità si trasforma da combinazione lineare convessa a combinazione lineare non-negativa, sui possibili esiti. Da qui a chiedere di rimuovere anche il vincolo di non-negativita' delle componenti, fino ad ottenere un vero e proprio spazio lineare di probabilità, il passo e' breve (almeno per Aaronson).

Si noti, però, che il carattere di spazio lineare è del tutto innaturale per uno spazio di probabilità: le distribuzioni di probabilità non si sommano fra di loro nè si fanno combinazioni lineari. La mossa verso uno spazio lineare, in questo ragionamento, è una mossa dettata completamente a posteriori dal fatto che uno spazio lineare sarà la base della meccanica quantistica (gli stati fisici, quelli sì, si sommano, ovvero si sovrappongono).
 

Le ampiezze complesse della meccanica quantistica sono legate al suo carattere probabilistico e "somigliano" alle probabilità stesse, ma il loro carattere lineare è completamente estraneo al tradizionale concetto di probabilità. Il passaggio presuppone, dunque, non solo un'estensione di dominio (da reale-non-negativo a complesso) ma un vero e proprio salto di struttura matematica. E' diffile accettare questo salto semplicemente come una "naturale generalizzazione" piuttosto che come un'analogia forzata.
 

Ma torniamo a questa presunta generalizzazione. In ogni caso queste componenti della combinazione lineare (non piu' non-negativa ne' convessa) non possono piu' essere interpretate direttamente come probabilità, ovvero messe a diretto confronto con le frequenze misurate sperimentalmente. Allora si decide di ricostruire una distribuzione di probabilità tramite un meccanismo di ri-non-negativizzazione (l'applicazione del modulo-quadro) di quelle componenti e, risalendo a ritroso, di ri-normalizzazione. E arriviamo dunque ad una 2-norma del vettore dello spazio lineare precedentemente costruito.
 

E' chiaro che tale procedimento, partito in qualche modo come semplificazione per il calcolo matematico (l'applicazione di un vincolo solo in fase finale) e dunque di carattere del tutto arbitrario e convenzionale, finisce per originare una struttura del tutto nuova (lo spazio lineare delle ampiezze) su cui imbastire uno spazio di probabilità esattamente identico a quello che si intendeva semplificare e/o generalizzare (fatto di componenti non-negative e normalizzate, il modulo quadro di quelle ampiezze).
 

Insomma, il concetto di probabilità non viene in alcun modo generalizzato (si tratta sempre di un'astrazione del limite per delle frequenze misurate sperimentalmente), ma semplicemente innestato su un substrato di spazio lineare che pretende di costituire il fondamento per l'evoluzione temporale e la combinazione di quelle distribuzioni di probabilità. Ovvero, pretende di costituire la fisica che soggiacie alle probabilità misurate sperimentalmente, esattamente come la fisica classica costituiva il substrato fisico per le distribuzioni di probabilità sperimentali, prima dell'analisi dei fenomeni atomici e microscopici. Con l'avvento della meccanica quantistica ci si è resi conto che le distribuzioni di probabilità sperimentalmente misurate (le distribuzioni di frequenze) devono essere descritte con un formalismo basato su uno spazio lineare. Ci si è poi resi conto che questa nuova fisica "lineare" aveva proprietà molto strane rispetto a qualsiasi cosa si fosse abituati (entanglment, disuguaglianze di Bell) e che fosse intrinsecamente probabilistica (differenza fra miscele statistiche e sovrapposizioni coerenti).
 

Ma tutto ciò ha a che fare con la fisica, non con la probabilità.

probabilità negative, ovvero: non poteva che essere meccanica quantistica

— La Meccanica Quantistica è quello a cui si arriva inevitabilmente se si parte dalla teoria della probabilità e si prova poi a generalizzarla in maniera che i numeri che usualmente chiamiamo "probabilità" possano essere negativi. In questi termini, la teoria avrebbe potuto essere inventata dai matematici nel XIX secolo senza alcun input sperimentale. Non è stato così, ma avrebbe potuto essere.

— Eppure, con tutte le strutture studiate dai matematici, nessuno di essi è giunto alla meccanica quantistica finchè l'esperimento non l'ha costretto.

— Questa è una perfetta esemplificazione del perchè gli esperimenti sono importanti. Quasi sempre l'unico vero motivo per cui abbiamo bisogno degli esperimenti è che non siamo abbastanza acuti. Una volta effettuati gli esperimenti, se abbiamo imparato qualcosa che valeva la pena sapere, è — si spera — proprio il perchè non era necessario partire con un esperimento, perchè non avrebbe avuto senso che il mondo fosse altrimenti. Ma eravamo troppo ottusi per capirlo da soli!

Scott Aaronson, PHYS771, Lecture 9
(mia libera traduzione)

 

Mi sarebbe piaciuto condividere, ma in fondo le cose non stanno proprio così.

...continua

   —   ∴   —   

Intendiamoci, i termini generali di una posizione simile sono del tutto condivisibili (hai la sensazione di aver capito davvero proprio quando ti accorgi che le cose non potevano essere altrimenti) e non esiterei a sottoscriverli per il caso della Relatività Speciale (e del resto Einstein non era partito affatto dai risultati dell'esperimento di Michelson-Morley) e forse ancor di più per la Relatività Generale. Ed è anche vero, per citare la teoria dell'evoluzione menzionata da Aaronson, che sebbene Darwin giunse alla sua intuizione dopo un prolungato periodo di osservazione della fauna delle Galapagos, tuttavia non ebbe bisogno di appoggiarsi alla teoria di Mendel sull'ereditarietà dei caratteri nè di conoscere il dogma centrale della biologia moderna che impedisce ai caratteri acquisiti à la Lamark di essere trasmessi alle generazioni successive.

Ma il caso della meccanica quantistica, secondo me, è profondamente diverso, soprattutto se guardato dal punto di vista che propone Aaronson, quello della probabilità.

Il concetto di probabilità nasce in simbiosi con quello di frequenza e non ha senso parlare di probabilità negativa neanche in meccanica quantistica. La novità matematica alla base della meccanica quantistica che, si sostiene, avrebbe potuto essere "inventata" senza inbeccata sperimentale, non è alcun concetto di probabilità negativa (o addirittura complessa). La novità è uno spazio lineare (con prodotto interno, uno spazio di Hilbert) come substrato dello spazio di probabilità, da cui derivare, cioè, la distribuzione di probabilità stessa come una p-norma dei vettori di quello spazio. Ma questa idea non ha alcun carattere di necessità, una teoria della probabilità non ha alcun bisogno di ergersi su uno spazio lineare. E del resto la meccanica quantistica vede in tale spazio lineare la natura fisica del mondo, un modello di realtà che, tra le altre cose, presenta caratteri di aleatorietà da descrivere per mezzo di distribuzioni di probabilità del tutto "tradizionali" (reali e non-negative). E se invece dalle solite miscele statistiche siamo arrivati a dover maneggiare cose terribili come le sovrapposizioni coerenti e le violazioni delle disuguaglianze di Bell (cose che nessun filosofo che si fosse divertito a distinguere fra probabilità epistemica e non-epistemica avrebbe comunque mai potuto immaginare), è perchè abbiamo dovuto fronteggiare una nuova fisica, non perchè abbiamo scoperto nuove proprietà matematiche del concetto di probabilità.

Certo, una volta accettata l'idea di uno spazio lineare da cui derivare distribuzioni di probabilità, ci sono ragioni di consistenza intrinseca e naturalezza che conducono a nient'altro che una 2-norma su uno spazio di Hilbert su campo complesso. E per questo vale assolutamente la pena di leggere la lezione 9 di Aaronson. Ma pensare che, per questo, il mondo non poteva non realizzare altro che la teoria della meccanica quantistica, significa non rendersi conto che la meccanica quantistica non è una teoria della probabilità, ma una teoria che fa uso della teoria della probabilità.

Al di là della questione particolare sollevata da Aaronson, comunque, siamo ancora ben lontani da una comprensione della meccanica quantistica à la "non poteva che essere così!". Ma forse non è questione di comprensione quanto, banalmente, che non siamo ancora arrivati alla teoria che "non poteva che essere così!"...

parte 2

NP-complete Problems and Physical Reality - 2

Ora, una delle congetture piu' ambiziose e difficili da dimostrare e' proprio quella secondo cui non esistono algoritmi capaci di risolvere i problemi NP-completi in un tempo polinomiale. E l'articolo di Aaronson [›››](gli antefatti sono qui, qui e nella precedente puntata)[‹‹‹] affronta esattamente tale questione, ma spostando l'attenzione da un punto di vista strettamente algoritmico ad uno piu' squisitamente fisico. La domanda e': non e' che l'impossibilita' di risolvere efficientemente i problemi NP-completi costitusce una vera e propria limitazione fisica nel nostro universo, esattamente come il limite della velocita' della luce o, forse meglio, come la seconda legge della termodinamica?

Vengono dunque passati in rassegna diversi tipi di dispositivi fisici che possono essere pensati e/o sono stati proposti, almeno in linea di principio, come calcolatori "naturali" capaci di rislovere, eventualmente specifici, problemi. A partire dal caso forse piu' famoso, quello delle bolle di sapone.

...continua

   —   ∴   —   

Avete i vostri n punti disposti su un piano e cercate l'insieme di segmenti, di lunghezza complessiva la piu' piccola possibile, che uniscano tutti i punti che avete scelto (i segmenti possono anche incontrarsi in altri ulteriori vertici rispetto ai punti scelti). Si puo' mostrare che questo tipo di problema e' proprio di tipo NP-completo. E puntualmente tutti gli algoritmi di soluzione finora proposti sono in grado di trovare la soluzione in un tempo che cresce esponenzialmente col numero di punti da collegare. Ora, e' un classico esempio di folklore scientifico quello di mostrare come sia possibile trovare la soluzione a un problema di questo tipo utilizzando delle bolle di sapone. Prendete due lastre di vetro tenute parallele da una serie di pioli fissati su entrambe le lastre proprio nelle posizioni dei punti del piano che avevate scelto. Immergendo le due lastre in un bagno di acqua e sapone, e poi risollevandole, e' possibile leggere la soluzione a questo problema nelle lamine di acqua e sapone che si formano tra i pioli (e la spiegazione e' che le bolle di sapone, per questioni energetiche, tendono a minimizzare la propria superficie...). Ora il punto in gioco non e' neanche quello che le bolle di sapone possono fare piu' di un calcolatore tradizionale (macchina di Turing). Si puo' infatti dimostrare che la fisica classica (delle lamine di acqua e sapone) puo' essere simulata per mezzo di "semplici" algoritmi polinomiali. Un esperimento di fisica, dunque, vorrebbe essere nientepopodimenoche' la dimostrazione che esiste un algoritmo tradizionale capace di risolvere un problema NP-completo in tempo polinomiale (pur non fornendo alcun esempio di tale algoritmo).

In realta' non c'e' nessuno scoop, perche', di fatto, non e' vero che l'esperimento delle bolle di sapone e' un buon metodo per risolvere il problema posto. O almeno non sempre. Quello che succede, infatti, e' che le lamine che si formano immergendo le lastre nell'acqua e sapone semplicemente tendono a rilassarsi verso una configurazione piu' stabile che minimizzi la loro superficie (e quindi la lunghezza complessiva dei segmenti corrispondenti). Ma non e' affatto detto che questo processo di assestamento si concluda nella configurazione ottimale in assoluto. Con pochi punti, questo e' quello che (spesso) succede davvero, ma aumentando pian piano il numero di pioli fra le lastre si osserva proprio che la formazione di lamine e' quasi del tutto casuale e, pur con occasionali "semplificazioni" verso configurazioni energeticamente piu' convenienti, risulta tutt'altro che la piu' conveniente.

Del resto c'e' tutta una classe di algoritmi tradizionali che tentano di risolvere istanze di problemi NP-completi proprio attraverso meccanismi di rilassamento verso "stati di minima energia" (come i vetri di spin). La difficolta' di questi algoritmi e' proprio quella della presenza di minimi locali che "intrappolano" l'esplorazione dello spazio delle soluzioni e fanno crescere esponenzialmente i tempi di rilassamento verso la soluzione ottimale cercata.

   —   ∴   —   

Interruzione, penserete voi, significa che sta passando ad un'altro dispositivo o fenomeno fisico. Invece no, c'e' un'ultima cosa da dire su questo punto. E lo stacco grafico ha il solo scopo di consentirmi di dare il necessario rilievo a quello che, secondo me, rappresenta uno dei passaggi piu' profondi dell'articolo di cui sto parlando. Un passaggio che consta di un paio di frasette buttate li' quasi semplicemente a concludere l'argomento, e che hanno invece provocato in me quella straordinaria sensazione che si prova quando si capisce qualcosa di semplice e profondo allo stesso tempo. Seguitemi.

Un esempio del tutto analogo a quello dei vetri di spin e delle bolle di sapone e' quello del ripiegamento delle proteine. Per quello che dicevamo sulla definizione della classe di problemi NP-completi, si potrebbe addirittura pensare di utilizzare delle proteine artificiali come calcolatori, mappando opportunamente la disposizione degli amminoacidi con i vincoli del nostro problema in maniera tale che la configurazione ripiegata della proteina fornisca una codifica per la soluzione al nostro problema di partenza. Ebbene, esattamente come nel caso delle bolle di sapone, nessuno puo' garantirci che il processo di ripiegamento della proteina artificiale non si "incagli" in minimi locali ben lontani dalla vera configurazione di minimo energetico.

Vi e' sorta spontanea la domanda centrale? Come diavolo fanno allora le proteine naturali a ripiegarsi correttamente in tempi rapidissimi? Vi siete gia' risposti? Evidentemente le proteine naturali si sono evolute specificatamente proprio per evitare di incontrare nel processo di ripiegamento, o di avere del tutto, minimi locali in cui incastrarsi (ed eccezioni a questa regola di buon adattamento sono date, per esempio, dai prioni...). [›››]Devo dire la verita': dopo il primo momento di estasi, mi sono anche ricordato che la stessa precisa sensazione l'avevo gia' provata proprio ad un seminario di biologia computazionale sul protein folding, neanche troppi anni fa. E' gravemente colpevole, l'essersene completamente dimenticati. Il fatto di non lavorare attivamente in quell'ambito di ricerca puo' fornirmi un appiglio per una scusa. Il fatto di aver speso del tempo, ora, per scrivere questi appunti sul blog potra' forse aiutarmi a non dimenticarmene ancora. O almeno non cosi' in fretta.[‹‹‹]

NP-complete Problems and Physical Reality − 1

Personalmente ho letto tutto l'articolo [›››](gli antefatti sono qui e qui)[‹‹‹] senza ricordarmi cosa fossero esattamente i problemi NP-completi. Se volete essere precisi potete andare sulla wikipedia oppure, molto meglio, potete divertirvi leggendo le lezioni di Aaronson (la quinta e la sesta in particolare, ma a quel punto il consiglio e' di partire dall'inizio...) dove l'ho ri-scoperto io stesso, dopo. Se siete pigri come me, puo' bastare sapere che con l'espressione NP-completi si fa riferimento ad una classe di problemi difficili, dove il concetto di difficolta' puo' essere espresso in maniera tecnicamente piu' precisa (ho scoperto che c'e' un variegatissimo zoo di classi di complessita'...).

In generale i problemi considerati sono caratterizzati da una grandezza variabile n (le cifre del numero da fattorizzare, la lunghezza della proteina da ripiegare...) e gli algoritmi che vengono proposti per risolvere tali problemi sono caratterizzati dalla maniera con cui scalano, all'aumentare di n, le risorse computazionali (memoria, tempo...) richieste dall'algoritmo per risolvere il problema. Ad esempio, un modo di vedere la difficolta' dei problemi NP-completi passa per la constatazione che qualsiasi algoritmo finora proposto per la loro soluzione richiede un tempo che cresce esponenzialmente con n. La definizione della classe di problemi NP-completi non fa esplicito riferimento allo scalare delle risorse richieste per la soluzione. Del resto quella e' una caratteristica di un algoritmo piu' che di un problema. Questo punto di come definire la "classe di difficolta'" di un problema senza far esplicito riferimento al "miglior algoritmo capace di risolverlo" e' molto interessante, lasciatemi spendere qualche parola in piu' (ma ovviamente sto semplicemente seguendo la lezione 6 di Aaronson...!).

   —   ∴   —   

Considerate il problema di saper dire, di un numero a n cifre, se e' primo o composto (senza necessariamente fattorizzarlo). Oppure considerate il problema di soddisfare il meglio possibile le richieste di alloggio in stanze doppie di un numero n di persone, ciascuna con l'indicazione di quale delle altre persone e' il suo "compagno di stanza preferito". Oppure ancora considerate il problema di sapere, date due sequenze di DNA lunghe n basi, quante inserzioni e rimozioni di basi sono necessarie per convertire una sequenza nell'altra. Ebbene, per questi problemi apparentemente difficili sono invece stati trovati (spesso dopo dozzine di anni di lavoro) algoritmi capaci di risolverli in un tempo polinomiale (un tempo cioe' che cresce "solo" come n ad una qualche potenza). Come possiamo distinguere, dunque, i problemi davvero difficili da quelli che semplicemente sembrano difficili?

Ebbene, uno dei risultati fondamentali della teoria di NP-completezza sviluppata nei primi anni 70 da Cook, Karp e Levin e' proprio il seguente: e' possibile dimostrare, per la maggior parte dei problemi "difficili", che essi rappresentano problemi della stessa difficolta'. Se fossimo in grado, cioe', di risolvere in tempo polinomiale uno solo di questi problemi, allora saremmo automaticamente in grado di fornire un algoritmo polinomiale anche per ciascuno degli altri problemi. Proprio come se ciascuno di essi fosse in realta' nient'altro che la riformulazione di un solo stesso problema.

Meccanica Quantistica, questa sconosciuta...

Come al solito le tentazioni piu' irresistibili arrivano legioni proprio quando meno puoi permettertelo.

E' da pochissimo che ho aggiunto i feed di questo blog fra i miei segnalibri, e oggi mi sono ritrovato con questo post che mi ha fatto scivolare irrimediabilmente a leggere la lezione 11 [›››](e' solo una coincidenza che anche con A fìrst Encyclopaedia of Tlön siamo partiti dall'XI volume?)[‹‹‹] e quindi anche la lezione 9...

Sono in ritardo sparato col lavoro, e proprio non ho tempo, ma − diavolo! − quanto avrei voglia di mettermi a leggere, ora, subito, adesso e tutti di filato, tutte le Further Reading citate in quest'ultima lezione!!!

Per ora mi limito a consigliarvi queste due lezioni, ma quanto prima (sigh!) approfondiro' la cosa: cerchero' di capire meglio chi e' questo Scott Aaronson, daro' sicuramente un'occhiata alle altre lezione del suo corso [›››](cazzo, cazzo, cazzo! Ma avete visto che titoli?!?)[‹‹‹], al suo apparentemente portentoso articolo e agli altri che cita, compreso questo e gli altri di questo tal Christopher A. Fuchs...

Come si fa a tornare a lavorare?!?

 

PS

Franco, qui c'e' pane anche per i tuoi denti!