Considerazioni generatore casuale nella progettazione di algoritmi randomizzati

Question

E 'ben noto che l'efficienza degli algoritmi randomizzati (almeno quelle in BPP e RP) dipende dalla qualità del generatore casuale utilizzato. fonti casuali perfetti non sono disponibili nella pratica. Anche se è dimostrato che per tutti $ 0 <\ delta \ leq \ frac {1} {2} $ l'identità BPP = $ \ delta $ -bpp e RP = $ \ delta $ -RP attesa, non è vero che l'originale algoritmo utilizzato per una sorgente a caso prefetto può essere direttamente utilizzato anche per un $ \ delta $ fonte -Random. Invece, un po 'di simulazione deve essere fatto. Questa simulazione è polinomiale, ma l'algoritmo risultante non è così efficiente come quella originale.

Inoltre, per quanto a mia conoscenza, i generatori casuali utilizzati nella pratica di solito non sono nemmeno $ \ delta $ -sources, ma fonti pseudo-casuali che possono comportarsi molto male nel peggiore dei casi.

Wikipedia :

Nella pratica comune, algoritmi randomizzati vengono approssimate utilizzando un generatore di numeri pseudocasuali in luogo di una vera sorgente di bit casuali; Tale implementazione può discostarsi dal comportamento teorico previsto.

In realtà, le implementazioni di algoritmi randomizzati che ho visto fino ad ora erano semplici implementazioni degli algoritmi per sorgenti casuali perfetti correre con l'uso di fonti pseudocasuali.

La mia domanda è, se non v'è alcuna giustificazione di questa pratica comune. C'è qualche ragione di aspettarsi che nella maggior parte dei casi l'algoritmo restituirà un risultato corretto (con le probabilità come in BPP resp. RP)? Come può la "approssimazione" menzionato nella citazione da Wikipedia essere formalizzata? Può la deviazione menzionato essere in qualche modo stimato, almeno nel caso previsto? E 'possibile sostenere che a Monte-Carlo randomizzato algoritmo di corsa su una fonte casuale perfetta si trasformerà in un algoritmo stocastico ben educati quando viene eseguito su una fonte di pseudo? O ci sono altre considerazioni analoghe?

Answer 1

Ecco una buona giustificazione. Supponiamo di utilizzare un crittografico resistenza generatore di numeri pseudocasuali per generare i bit casuali necessari per qualche algoritmo randomizzato. Poi l'algoritmo risultante continuerà a funzionare, a patto che l'algoritmo di crittografia è sicuro.

crittografico resistenza generatore di numeri pseudocasuali è uno strumento standard dalla crittografia che accetta un breve seme (per esempio, 128 bit di casualità vero) e genera un numero illimitato di bit pseudocasuali. Viene fornito con una forte garanzia di sicurezza: finché il sottostante crittografica primitivo non è rotto, allora i bit pseudocasuali sarà completamente indistinguibile da bit true-casuali con qualsiasi procedimento fattibile (e, in particolare, nessun algoritmo efficiente può distinguere la sua uscita da una sequenza di veri bit casuali). Per esempio, si potrebbe ottenere una garanzia che dice:. Se il factoring è difficile (o, se RSA è sicuro, o, se è sicuro AES), allora questo è un generatore di buona pseudo

Questa è una garanzia molto forte, dal momento che è ampiamente creduto di essere molto difficile da rompere queste primitive crittografiche. Per esempio, se si riesce a capire un modo efficace per fattore di numeri molto grandi, allora sarebbe un risultato importante passo avanti. Per tutti gli scopi pratici, si può agire come se le primitive crittografiche sono infrangibili. Ciò significa che, per tutti gli scopi pratici, si può agire come se l'uscita di un crittografico resistenza generatore di numeri pseudocasuali è fondamentalmente la stessa fino a quando una sequenza di bit true-casuali. In particolare, si tratta di una fonte bene della casualità necessaria da un algoritmo randomizzato.

(ho sorvolato il fatto che, per usare un PRNG cripto-forza, è ancora bisogno di trovare 128 bit di casualità vero sul proprio per formare il seme. Ma di solito questo non è difficile, e in effetti, non ci sono strumenti crittografici per assistere con questo compito pure.)

In pratica, ottenendo estremamente buone bit pseudocasuali è semplice come

$ cat /dev/urandom

Answer 2

E 'ben noto che l'efficienza degli algoritmi randomizzati (almeno quelle in BPP e RP) dipende dalla qualità del generatore casuale utilizzato. devo disaccordo. Che una buona sequenza di pseudurandom insieme ti dà è una garanzia sulle prestazioni dell'algoritmo di eseguire una sequenza casuale dal complesso, rispetto ad una sequenza trully casuale. Se non si dispone di una tale garanzia, non si può concludere che l'algoritmo funziona male -. Basta non si sa

C'è qualche giustificazione di questa pratica comune? Funziona.

E 'possibile sostenere che a Monte-Carlo randomizzato algoritmo di corsa su una fonte casuale perfetta si trasformerà in un ben educati algoritmo stocastico quando viene eseguito su una fonte pseudo? Complessità soffre di teoria da due difetti . Il primo è che è molto difficile dimostrare niente (per esempio, P vs. NP è aperto). La seconda è che è principalmente riguarda analisi del caso peggiore. Messi insieme, questi due limiti escludono la teoria della complessità come un buon modello per il comportamento degli algoritmi nella pratica.