Scopo della randomizzazione / dedandomizzazione nell'algoritmo randomizzato di base per Max Sat

Question

nelle sezioni 5.1 di La progettazione di algoritmi di approssimazione di Williamson e Shmoys, descrivono a Algoritmo randomizzato di base per Max Sat e come dervardomizzarlo. L'algoritmo è solo per assegnare ogni variabile 1 (true) con probabilità 1/2 e 0 (falso) con probabilità 1/2. In altre parole, campione uniformemente a caso dallo spazio di tutte le soluzioni. Mostrano che questa è un approssimazione 1/2.

Poi nella Sezione 5.2, descrivono come dervardomizzarlo usando il metodo delle aspettative condizionali. (Non descriverò il processo qui perché non è molto complesso e ampiamente noto che sto assumendo.)

La mia domanda è, perché disturbare derbandomizzare in questo modo? O anche, perché preoccuparsi di fare l'algoritmo casuale in primo luogo?

Mi sembra che un algoritmo altrettanto buono sarebbe l'unico liner che stabilisce deterministicamente tutte le variabili a 1. Dato un po 'di istanza del SAT max come input, mi sembra che tu ci aspetterebbe anche (cioè "in aspettativa che sarebbe ") soddisfare la metà delle clausole. Per me, l'analisi dell'algoritmo casuale sembra davvero dire che qualsiasi ipotesi fissa è "buona". (Piuttosto che dimostrare che il nostro algoritmo casuale è intrinsecamente buono.) Allora perché attraversare il processo di randomizzazione e dervadomizzazione in primo luogo?

Grazie in anticipo!

Answer 1

La differenza è che l'algoritmo randomizzato garantisce un previsto 1/2-approssimazione su qualsiasi ingresso . Al contrario, è facile per un avversario costruire un input (cioè un'istanza di max-sat) per la quale la deterministica "imposta tutte le variabili a true" algoritmo satisifes clausole zero.

Ricordare che lo spazio campione per un algoritmo randomizzato è su un insieme di bit casuali ausiliari. Non esiste una distribuzione di probabilità assunta su ingressi . L'obiettivo tipico del design ad algoritmo randomizzato è per ogni input da gestire bene in attesa. (Analisi del comportamento dell'algoritmo su una distribuzione di input assunta si chiama Analisi della custodia medio invece.)

Quali sono i bit casuali ausiliari?

Supponiamo di avere una macchina di tinger randomizzata $ M_1 $ che funziona su istanze di lunghezza $ N $ Per non più di $ t (n) $ tempo, durante il quale non fa più di $ r (n) \ le T (n) $ decisioni casuali. Possiamo trasformare questa macchina in deterministic macchina di turing $ M_2 $ che ha due nastri di ingresso: il normale nastro che contiene la stringa di ingresso < class="container math"> $ x $ di lunghezza $ n $ e un nastro che contiene una stringa $ R $ di lunghezza $ r (n) $ . La stringa $ r $ è la nostra stringa di bit casuali ausiliari ; Determina quali decisioni "casuali" è quella di fare. Quando diciamo che la macchina randomizzata di Turing run $ m_1 (x) $ accetta con probabilità $ p $ , Questo equivale a dire che il set $$ A (x)=sinistra \ {r \ | \ r \ in \ {0, 1 \} \ \ {r (| x |)}, m_2 (x, r ) \ testo {accetta} \ destra \} $$ di $ R $ stringhe che rendono $ M_2 (x, r) $ Accetta costituisce una frazione $ p= | A (x) | / 2 ^ {| x |} $ del set di tutti i $ r $ stringhe.

Potresti riconoscere ciò che sta succedendo qui se hai visto la costruzione analoga per macchine per la Turing nonerministic. Possiamo pensare a una macchina NP come una macchina nonreterministica che si ramifica in esponenzialmente molte copie di se stessa. Ma possiamo anche pensarci come una macchina deterministica verificatore che richiede sia un ingresso che una stringa "Proof", con i criteri di accettazione che una stringa di ingresso è nella lingua se qualsiasi Stringa a prova rende la macchina accettata.

È spesso più facile pensare a questo concetto down-to-earth di macchine deterministici e quali sottoinsieme di stringhe di prova rende la macchina accettata su un dato input, piuttosto che pensare a idee molto astratte come le macchine esponenziali di ramificazione e possibili mondi . E rende più facile definire classi di complessità come Co-NP, PP, BPP, ⊕P, ecc., Tutti sono essenzialmente "NP con una regola di accettazione diversa". Ad esempio:

.
• np è il set di lingue $ l $ per il quale esiste una macchina del verificatore polinomiale $ M_2 $ < / span> in modo tale che $ x \ in l $ se e solo se esiste una classe $ R $ stringa Tale $ M_2 (x, r) $ accetta (dove la lunghezza della $ r $ stringa è limitato da un polinomio $ r (| x |) $ ).
• bpp è il set di lingue $ l $ per il quale esiste una macchina del verificatore polinomiale $ m_2 (x , r) $ in modo tale che $ x \ in l $ implica che $ m_2 (x, r) $ accetta almeno ⅔ di $ r $ stringhe e $ x \ Notin L $ implica Quella $ M_2 (x, r) $ accetta al massimo ⅓ di $ r $ stringhe (dove il Lunghezza della $ R $ Le stringhe sono delimitate da un polinomio $ r (| x |) $ ).

Nota: per lo più non importa se abbiamo bisogno della $ R $ stringhe di avere lunghezza esattamente $ R (N) $ o al massimo $ r (n) $ , dal momento che consente solo stringhe più brevi Aumenta il numero di possibili stringhe da un fattore costante.