Il 5 agosto il nuovo leader del parlamento iraniano ha prestato giuramento davanti al sacro corano:

http://www.repubblica.it/2009/08/sezioni/esteri/iran-7/ahmadinejad-giura/ahmadinejad-giura.html

Ma si può giurare se le elezioni sono state truccate? E come faccio a saperlo? Non sono io ma è la statistica che parla: A pagina 6 fig. 6 di questo link potete vedere un bel grafico in cui sul 7 tre pallini non sono allineati rispetto a quello che ci aspettavamo. Cosa vuol dire? Praticamente prendete il numero di votanti per ogni seggio del candidato Karroubi, avremo 366 numeri (ci sono 366 seggi), ora prendere la prima cifra decimale di questi numeri, gli statistici sanno da anni che il numero di 1 deve essere circa il 30 %, il numero di 2 il 17%, il numero di 3 il 12%, etc. Di quelli con il 7 ce ne devono essere il 6%, invece ce ne sono l’11%.

La probabilità che questo succeda? Minore dello 0.02%

Oppure hanno fatto dei brogli.

Annunci

Tre settimane fa sono stato ad un workshop intitolato “Limits of approximation algorithms: PCPs and unique games“, il viaggio mi è stato pagato molto gentilmente dal DIMACS. Bella università nel New Jersey. Ma se non avete la macchina scordatevelo.

Provo a dare una spiegazione vaga dei complicati, intricati, probabilistici, fouriertici, tecnici ma affascinanti concetti in questa area della computer science.

Cos’è una PCP? E’ una dimostrazione controllabile probabilisticamente, cioé una dimostrazione matematica che può essere controllata guardandone solo una parte in posti casuali. E’ qualcosa di più, è verificabile localmente, cioé abbiamo bisogno di pochi bit. Veramente soltanto un numero costante di bit, 3.

Niente di strano sotto il sole, prendiamo la nostra dimostrazione matematica preferita, applichiamo qualche trucco di teoria dei codice a otteniamo una dimostrazione con una ridondanza più alta. La tecnica usata qui è la trasformata di Fourier sul cubo booleano, strumento magnifico e versatile. (Da non perdere il teorema sulla stabilità della maggioranza, proprio fico)

Dall’altra parte abbiamo niente popò di meno che NP, la classe dei problemi la cui soluzione può essere verificata in tempo polinomiale. Questa classe è davvero grande. Per esempio un problema che è in NP è quello di soddisfare tutte le clausole in un insieme \{x_{i_1} \vee x_{i_2} \vee x_{i_3} | i_1,i_2,i_3 \in [1,n], x_{u}\in\{vero,falso\}\} , dove ogni clausola è un OR di tre variabili, ovviamente ci possono essere dei NOT. Questo problema è chiamato MAX 3-SAT. Una soluzione può essere controllata in tempo polinomiale. Trovarla potrebbe richiedere tentare tutte le possibilità.

Ora immaginiamo di essere più modesti e voler semplicemente massimizzare il numero di clausole soddisfatte per una istanza del problema. Un algoritmo molto semplice è il seguente: provare molte assegnazioni casuali! Se ci si pensa per un attimo si vede che l’approssimazione di questo algoritmo è \frac{7}{8} , cioé ci aspettiamo che questo algoritmo soddisfi \frac{7}{8} delle clausole soddisfacibili. Non male per una scimmia batti-tasti.

Ok, ora arriviamo alla difficoltà di approssimare: non possiamo ottenere un algoritmo che in tempo polinomiale, per questo problema, fa meglio della scimmia! Intendo dire che, se l’algoritmo riesce a darci \frac{7}{8} + \epsilon clausole soddisfatte allora P sarebbe uguale a NP e come direbbe un mio amico, saremmo come Dio oppure ci accontentiamo di 1’000’000 di dollari.

Ottimo. Dov’è la PCP? Una dimostrazione di Hastad che NP = PCP(3 queries, log(n) random bits) implica il fatto precedente.

L’argomento principale del tutorial è la Unique Games Conjecture, vedi la parte 2.

Un buon riferimento, in inglese, è Computational Complexity: A Modern Approach

A breve tradurrò il mio post sulle donne del governo che ho pubblicato nella versione in inglese del blog

Nel frattempo segnalo questa rocambolesca notizia del tg1 che riesce a non menzionare il nome di Mara Carfagna:

Non è giovane perché è ministro, è ministro perché è giovane e l’ha data a Silvio Berlusconi

Il propagandista

agosto 1, 2009

Subito dopo la propaganda di Berlusconi ho trovato
un’altra sua intervista molto interessante da commentare:

L’idea di questi video però NON è attaccare Berlusconi. L’idea è mostrare come i mezzi di comunicazione possano essere manipolati da chi ha degli interessi.

C’è differenza tra SAPERE di essere ripreso e NON SAPERLO. La differenza è che nel secondo caso si è sinceri e diretti, nel primo invece si tiene conto delle “apparenze”.

Anche Barack Obama è un propagandista, fatto e finito.

Se proprio devo dare addosso a Berlusconi, devo dire che è un barbone: si veste sempre uguale (identico!), ha sempre la stessa macchina da sette anni, una Audi A8 blindata. L’elicottero e gli aerei non contano, li usa per lavoro. Solo da poco ha cambiato Yacht: un vela a motore da 48 metri, costruito da una sua azienda toscana con sede alle Bermuda!