Limiti di approssimabilità: PCP e Unique Games (Parte 1: PCP)

agosto 10, 2009

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

Annunci

Una Risposta to “Limiti di approssimabilità: PCP e Unique Games (Parte 1: PCP)”

  1. Riccardo said

    Il mio sogno erotico è proprio la cubista sul cubo booleano, strumento magnifico e versatile se flessibile come dico io! 😀
    Scherzi a parte, questo post mi mette di fronte alla mia ignoranza abissale… vado a meditare…

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: