Dopo aver pubblicato qualche tempo fa il materiale della mia tesi triennale, ho deciso di mettere online anche il colloquio del mio quarto anno in Normale (Archived), che tratta della derandomizzazione dei giochi di Arthur-Merlin (Archived).
Per le (immagino molte) persone che non lo sapessero, gli algoritmi di tipo Arthur-Merlin sono protocolli interattivi in cui Merlin deve dimostrare ad Arthur di sapere qualcosa, mandando ad Arthur un singolo messaggio, e Arthur può accettare o meno utilizzando una computazione in BPP (Archived), cioè probabilistica in tempo polinomiale.
Invece, "derandomizzare" una classe di complessità consiste nel trovare un modo di mostrare che si può fare a meno di certi tipi di estrazione casuale ed utilizzare invece algoritmi deterministici che simulano tale casualità.
L'esempio naive di come ciò si possa fare, incluso anche nel pdf del colloquio, è semplicemente quello di calcolare la probabilità che l'algoritmo probabilistico ritorni un certo risultato per enumerazione della stringa di bit random. Questa è chiaramente una riduzione "dispendiosa", ma permette già di dire che se un algoritmo BPP utilizza al più O(\log n) bit casuali allora può essere simulato in P.
Il colloquio si spinge poi a spiegare l'idea di come si possa derandomizzare Arthur-Merlin utilizzando gli Hitting Sets, ovvero dei sottoinsiemi delle stringhe "random" tali che se l'algoritmo probabilistico dà risultato affermativo con una certa probabilità, allora vi è un rappresentante nell'hitting set di questo risultato affermativo.
La spiegazione è un po' lunga e nel colloquio mi limito ad evidenziarne i punti salienti per renderla comunque comprensibile. Potete trovare qui il pdf risultante.