Showing posts with label sylvie coyaud. Show all posts
Showing posts with label sylvie coyaud. Show all posts

17 August 2010

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

07 January 2009

global warming, global warning? - 3

Le considerazioni di questo post mi frullano per la testa da prima delle vacanze di Natale. Ora però sembrerà che siano l'ennesima reazione alla notizia sull'estensione dei ghiacci al Polo Nord
In realtà è da tempo che sono sempre più confuso, in pratica da quando ho aggiunto i feed di climatemonitor al mio gReader.
Va bene il principio di autorità, ma vorrei che le mie autortià — sylvie, ad esempio, o Carletto Darwin, o weissbach... giusto per dirne alcune — provassero a suggerire anche un abozzo di risposta, ad esempio, ad obiezioni ben assestate come quella secondo cui la capacità di assorbimento della CO2 sarebbe già correntemente saturata, come, ancora, non ci sarebbe questa grande correlazione fra l'aumento di concentrazione di CO2 e variazioni di temperatura. Oppure a quella secondo cui all'effetto serra contribuirebbe molto più, ad esempio, il vapor acqueo rispetto alla CO2, e comunque il loro effetto sulla temperatura globale sarebbe di gran lunga minoritario rispetto ad altre e ben più rilevanti variabili climatiche come la forzante solare (che, en passant, non vuole saperne di ripartire), i cicli di temperature oceaniche (Pacific Decadal Oscillation, PDO) o le frequenze relative di El Niño rispetto a La Niña.
Insomma, qualcosa con cui rispondere a quel che beppe caravita chiama il controcanto all'ICPP.
Senza sfida, sinceramente, per (tentare di) capire.

18 June 2007

global warming, global warning? - 2

Dopo gli scettici, ecco i creduloni. Ma sono creduloni coi controcoglioni, mica oche qualsiasi. Ecco qui la prima puntata di una "chiacchierate" sul tema, e qui la seconda.
E’ impressionante la vastita’ di informazioni e notizie che Sylvie riesce a snocciolare come se niente fosse, ribattendo colpo su colpo in maniera impeccabile. Questo e' vero giornalismo.
 
PS
Senza offese per Andrea, il gioco e' forse reso facile dalla debolezza delle sue argomentazioni. Forse sarebbe piu' interessante se nel dibattito intervenisse Maurizio Morabito, che nel suo dialogo mi era sembrato citare fonti e notize (una qualche interazione in effetti c'e' stata, ma giusto un semplice "contatto"...). Maurizio, la scrivi tu una mail alla nostra Sylvie? Che poi magari l'oca sapiens ci pubblica la sua controrisposta?
Per quanto mi riguarda, per ora, forse perche' e' l'ultima campana che ho sentito, mi viene da andar dietro alla Coyaud...

21 May 2007

Rassegna (ragionata) di link post fine settimana

UPDATE-2:
L'UAAR commenta meglio di me l'articolo dell'Avvenire... (da)
 
UPDATE:
Oggi (21/5/2007) c'e' gia' un altro post sul blog di Luttazzi e parla... del suo nuovo ultimo libro. Dovevo immaginarlo... :(
 
  • Il contrappunti di oggi di Mantellini torna ancora sulle potenzialita' della rete, ma questa volta con esempio concreto dall'attuale presente: da leggere fino in fondo.
  • Ora a Trento c'e' La scimmia nuda: "Come diceva Voltaire, la liberta' di pensiero va difesa soprattutto quando e' un pensiero che non condividiamo [...], ma..."
  • Ancora su Sex crimes and the Vatican, in italiano: l'intenzione di Santoro di comprare i diritti dell'inchiesta BBC e mandarla in onda sulla sua trasmissione ha fatto fare il balzo di qualita' alla notizia che, finalmente, comincia a circolare sui siti dei giornali "a tiratura nazionale" come repubblica.it e corriere.it (non ho notizie del mondo "reale" di carta stampata e TV: qualcuno ha sentito niente su quei canali?). Ovviamente la notizia non e' quella del servizio della BBC (ne' del fatto che in italia se ne sa qualcosa solo ora e grazie a internet, non mi stanchero' di ripeterlo!) quanto la "controversa" decisione di Santoro (mah...). L'Avvenire entra invece nel merito del contenuto del video. Da notare le due clamorose smentite che dovrebbero smontare l'inchiesta: prima di tutto il Crimen sollicitationis risalirebbe al lontano 1962, ben prima che Ratzinger diventasse prefetto della Congregazione per la dottrina della fede (e' infame, dunque, l'accostamento che l'inchiesta della BBC fa tra quel documento e il nome di Ratzinger: il fatto che sia stato proprio Ratzinger, nel 2001, a menzionare esplicitamente quel documento, per la prima volta pubblicamente, in una lettera ai vescovi del mondo, per insistere sul modo con cui fronteggiare le accuse sugli abusi sessuali minorili da parte di preti cattolici... be', e' evidentemente un fatto del tutto irrilevante!); in secondo luogo, il fatto che la Chiesa pretendesse assoluta riservatezza, pena scomunica, sui casi trattati e persino sulle vittime degli abusi non era affatto dovuta alle esigenze di coprire i numerosi scandali avvenuti negli Stati Uniti, bensi' trattavasi di semplice tutela delle parti prima della sentenza definitiva (come quelli della BBC abbiano potuto essere cosi' maliziosi proprio non si riesce a capirlo...).
  • Forse quest'altra notizia non meirtava un item a parte, ma andava inserita in quello qui sopra...
  • L'ultimo post di Luttazzi conferma che sta effettivamente riprendendo ad aggiornare con una qualche (pur non frenetica) regolarita' il suo blog.
  • Il mercato delle acque in bottiglia non mi e' mai piaciuto: leggete cosa sta succedendo vicino a Milano.

02 May 2007

Sylvie, l'Internet delle cose e la Grid

L'Oca Sapiens mi chiama direttamente in causa: potevo non risponderle?
Siccome pero' la domanda mi ha spinto a riflessioni sparse, di carattere piu' generale, e la risposta stava diventando troppo lunga, ho pensato di dedicarle un post qui sul mio blog.
   —   ∴   —   
Sylvie mi chiede cosa ne penso dello special report dell'Economist di questa settimana. Io non ho una copia cartacea dell'Economist e l'inchiesta integrale e' disponibile online solo previa registrazione a pagamento. Gratuitamente e' comunque disponibile una specie di sintesi da cui si evince che l'inchiesta discute della progressiva diffusione delle tecnologie informatiche negli oggetti quotidiani e in particolare della "rete delle cose" che dovrebbe nascere quando le attuali tecnologie wireless consentiranno a questi dispositivi di collegarsi e parlare fra di loro.
Piu' che il sottoscritto, una persona giusta a cui chiedere un parere potrebbe essere Stefano Quintarelli, oppure Alfonso Fuggetta (che in effetti ha scritto un articolo precisamente sull'inserto dell'Economist), oppure ancora a Beppe Caravita (anche lui commenta alcuni passaggi dell'inchiesta, vedi anche qui).
Cosa mai potrei aggiungere, io? Forse solo sottolineare che un punto chiave perche' qualcuno degli scenari che si immaginano quando si pensa alla "rete delle cose" possa davvero realizzarsi e' quello dell'esistenza di standard aperti e universali, su cui costruire servizi aggiuntivi e "intelligenti". Questo e' un punto cruciale (come si deduce dalla storia del web) e tuttavia non e' affatto ovvio che sia semplice da realizzare per delle "cose concrete" cosi' come lo e' stato per le "comunicazioni astratte" di Internet.
Questo mi porta naturalmente a fare l'esempio di Grid, perche' sin dalla nascita viene pensato esattamente come una sorta di "evoluzione" di Internet, da rete dalle informazioni a rete di risorse. Il fatto e' che secondo me questo paragone e' fortemente fuorviante.
Sin dalle loro origini, il web e la Grid hanno percorso strade completamente diverse. Il web e' nato crescendo piu' o meno per caso lungo una via che a posteriori forse si puo' giudicare inevitabile, ma che non e' mai stata perseguita esplicitamente. Cos'e' il web oggi (ebay, i web-service ma soprattutto i blog, il nanopublishing, il social web, l'XML...), nessuno avrebbe saputo dirlo quando e' nato 10 anni fa; cosa diventera' domani nessuno lo sa davvero oggi, perche' segue delle strade tutte sue, piene di contingenza e di necessita', anche se la necessita' la si scopre sempre a posteriori. Esattamente come l'idea della vita che dobbiamo a Darwin (e, per quanto mi riguarda, devo a Stephen Jay Gould). La forza del protocollo IP e dell'HTTP, la loro semplicita' e la loro universalita', era una naturale caratteristica della cosa che si voleva mettere in rete: un file di testo, dei caratteri. Da quella semplicita' sono emerse poi, pian piano, tutte le mille sfaccettature che vediamo oggi, ma non si puo' non notare che si tratta ancora essenzialmente di una rete di informazioni.
Con la Grid, invece, e' stato esattamente l'opposto. La sua stessa idea non e' nata per aggregazione come una valanga da una palla di neve che pian piano comincia a rotolare lungo un pendio, ma e' stata studiata a tavolino e sono stati stanziati ingenti finanziamenti per cercare di realizzarla. E cercare di realizzarla e' risultato dannatamente difficile. Il problema e' dovuto al fatto che si sta cercando di mettere in comunicazione degli oggetti estremamente complessi (esattamente l'opposto di un file di testo), per fare cose ancora piu' complesse. La Grid vorrebbe mettere a disposizione risorse di calcolo e storage, ma non basta mettere in rete dei computer per avere a disposizione le loro CPU e i loro spazio disco. Vuoi usare la CPU del mio cluster? Devi dirmi cosa vuoi fare, che programma vuoi far girare e se il programma occupa spazio e costa trasferirlo, vorresti che fosse gia' presente sulle macchine del cluster, ma allora devi dirmi che versione del programma vuoi... e l'input? me lo mandi con la descrizione del programma che vuoi che esegua? e l'output? lo metto in qualche risorsa di storage della Grid? e' piccolo e quindi te lo restituisco direttamente quando ho finito? et cetera. E il problema e' che ogni possibile utilizzo diverso delle risorse puo' pretendere specifiche tutte sue e non appena ti rendi conto di un possibile nuovo utilizzo della risorsa devi riaggiustare i protocolli perche' riescano a gestire anche questa nuova possibilita'.
Si tratta, essenzialmente, delle stesse difficolta' che si incontrano nei tentativi di realizzare il web semantico, anch'esso dipinto come un'evoluzione del web (e sponsorizzato dallo stesso inventore del web, Tim Berners-Lee). E tuttavia le piramidi strutturali di Internet e di Grid (e del web semantico) sono letteralmente invertite: la complessita' si e' sviluppata sopra Internet, mentre con la Grid la si vorrebbe tenere nascosta sotto, lasciando in superficie un utilizzo il piu' semplice possibile per l'utente finale che vuole accedere alle risorse.
Per tornare al futuro delineato dall'inchiesta dell'Economist, la vedo piu' o meno allo stesso modo: e' facile mettere un po' di "cervello" (i cosiddetti sistemi embedded) a un frigorifero e a una lavastoviglie, per non parlare del fatto che i cellulari ormai "sono morti"). E' piu' difficile metterli in comunicazione (e vanno bene queste nuove tecnologie wireless) in maniera abbastanza sofisticata da permetter loro di far qualcosa con quella comunicazione. Con Internet siamo noi che comunichiamo. Far comunicare delle cose, pur sofisticate come possono essere le risorse della Grid, e' tutt'un'altra storia.
 
Prima di smetterla, una precisazione.
Ho soltanto accennato alle molte difficolta' che si devono affrontare per mettere in piedi una infrastruttura di Grid. Se messe accanto alla facilita' con cui si e' sviluppato il web e all'immenso e pressocche' immediato successo di Internet, possono lasciar pensare che la Grid sia un po' un fallimento. In realta' il punto e' prorpio – ed e' questo che volevo sottolineare – che il paragone non ha senso. L'(epi)fenomeno di Internet e l'impresa di allestire un'infrastruttura di Grid sono due cose completamente diverse. E per quanto i progressi fatti e i risultati ottenuti per la Grid siano molto meno appariscenti dell'evoluzione vertiginosa del web [›››], si tratta comunque di una strada obbligata, almeno per quanto riguarda le sfide di un'impresa come quella di LHC. Certo, poi le competenze maturate e la tecnologia sviluppata per il modello di grid compunting potra' e sara' esportata – anzi lo e' gia' – in altri ambiti come quello astro-/geo-fisico, biomedico, bioinformatico, economico-finanziario, fino alla protezione civile e ad ambiti piu' strettamente industriali. Ma per LHC non era molto una questione di scelta. Quando il nuovo acceleratore entrera' in funzione ed andra' a regime, verranno prodotti una quantita' di dati mai vista prima (ad un ritmo di una dozzina di PByte all'anno, P = peta = dieci alla 15). E questi dati dovranno poter essere accessibili e poter essere analizzati in qualsiasi momento da qualsiasi centro di ricerca sparso per il globo. Nessun centro, da solo, poteva fornire tutte le risorse necessarie. E l'integrazione e la coordinazione di tali risorse geograficamente distribuite conduceva naturalmente ad una soluzione di tipo grid computing.

19 April 2007

l'oca, le api e i cellulari

Con questo post, l'oca sapiens Sylvie Coyaud prova a rimettere in una giusta prospettiva la presunta notizia che sta facendo il giro del mondo in questi giorni, secondo cui le onde elettromagnetiche dei cellulari sarebbero la causa della scomparsa in massa della api.
In realta' i casi di pessima divulgazione scientifica sono frequentissimi: quando si parla di scienze, ma anche piu' semplicemente di tecnologia, praticamente tutti i giornali (lastampa.it, bisogna ammetterlo, in genere fa eccezione) sono pieni di grossolane imprecisioni e fortissime distorsioni.
Ma insomma, avevo semplicemente bisogno di un pretesto per rendere omaggio a Sylvie! :) [›››]