Sono randomizzati algoritmi costruttiva?

Question

Da, le prove nel metodo probabilistico sono spesso detto di essere non costruttivo.

Tuttavia, una prova con il metodo probabilistico progetta infatti un algoritmo randomizzato e lo utilizza per provare l'esistenza. Citato da P103 di Randomized Algorithms Con Rajeev Motwani, Prabhakar Raghavan :

Si potrebbe vedere la prova con il metodo probabilistico come uno studio randomizzato algoritmo. Questo sarebbe quindi necessaria un'ulteriore analisi che delimita il probabilità che l'algoritmo non riesce a trovare un buon partizione su un data esecuzione. La differenza principale tra un esperimento mentale in il metodo probabilistico e un algoritmo randomizzato è la fine che ciascuno rendimenti. Quando usiamo il metodo probabilistico, siamo solo trattasi di mostrare che esiste un oggetto combinatorio; in tal modo, abbiamo sono contento di mostrare che un evento favorevole si verifica con diverso da zero probabilità. Con un algoritmo randomizzato, d'altra parte, l'efficienza è una considerazione importante - non possiamo tollerare una minuscola probabilità di successo.

Quindi mi domando se algoritmi randomizzati sono visti come non costruttiva, ma lo fanno uscita una soluzione al termine di ogni corsa, che può o non può essere una soluzione ideale.

Come è un algoritmo o una prova "costruttivo" definito?

Grazie!

Answer 1

Il metodo probabilistico è tipicamente usato per mostrare che la probabilità di alcuni oggetto casuale avente una certa proprietà è diverso da zero, ma non presenta alcun esempio. Lo fa garanzia che un algoritmo di "repeat-until-successo" finirà per terminare, ma non dà un limite superiore sul runtime. Quindi, a meno che la probabilità di una partecipazione proprietà è sostanziale, una prova dell'esistenza con il metodo probabilistico rende un pessimo algoritmo.

In punto di fatto, algoritmi probabilistici non sono in realtà prove di esistenza costruttive, tanto quanto sono algoritmi per prodotti prove esistenza costruttive. L'uscita è un oggetto del tipo che è stato concepito per dimostrare l'esistenza di; ma il fatto che esso casualmente yield uno ( "non esisterà un'iterazione in cui si produce un esempio - se non con probabilità nulla ...") non è sufficiente per essere costruttivi; sarà soddisfacente a qualcuno che accetta già che i suffissi non-zero-probabilità-senza-costruzione per l'esistenza solo. Al contrario, se si dispone di una buona legata sul run-time, allora non c'è in linea di principio non è una scusa per non farlo funzionare al fine di produrre in realtà un esempio. Un buon algoritmo probabilistico non è ancora una dimostrazione costruttiva, ma un buon piano per ottenere una dimostrazione costruttiva.

Si noti che questa idea, che un algoritmo randomizzato è un strategia di prova (al contrario di una prova in sé) per dimostrare una quantificazione esistenziale, non è dissimile l'idea che l'induzione è una strategia a prova di buona per mostrare una quantificazione universale (sopra i numeri naturali). Questa analogia può sembrare convincente, come l'induzione è essenzialmente il cuore di ricorsione come una tecnica di calcolo. (Per ogni intero positivo $ n $, se si vuole decidere se $ n ^ 2 $ è una somma dei numeri dispari consecutivi precedenti $ 2n + 1 $, è possibile ridurre questo per indagare se $ (n-1) ^ 2 $ è una somma dei numeri dispari consecutivi precedenti $ 2n-1 $, e così via.) l'induzione è essenzialmente un a prova di strategia algoritmica che abbiamo elevato a un teorema, che ci permette di avere la conoscenza senza esplicitamente calcolare ogni volta. Tuttavia, l'induzione è accettata costruttivamente perché è già un assioma (-scheme) di Peano, e uno che è indipendente dagli altri assiomi. Al contrario, non v'è alcuna regola di inferenza o assioma che permette al metodo probabilistico per dimostrare l'esistenza in modo costruttivo, oppure in maniera costruttiva dimostrare che gli algoritmi probabilistici producono prove dell'esistenza o nulla in questo senso. Semplicemente non si può provare che non vi sono esempi di una classe di oggetti dal fatto che ci sia un algoritmo probabilistico per costruirlo, a meno che già accetta questa tesi, sia come un assioma, o da altri locali.

Naturalmente, si potrebbe adottare una posizione filosofica intermedia al costruttivismo e il classico approccio all'esistenza, e dire che ciò che si vuole non è costruzioni di per sé ma la costruzione-schema che sono lasciata fallire con qualsiasi probabilità meno di un; che renderebbe qualsiasi costruzione probabilistica "schematica", se non completamente costruttivo. Dove si vuole tracciare la linea, per dire che trovano una prova dell'esistenza "soddisfacente", in ultima analisi, dipende da quanto l'intuizione (in un certo senso non-filosofica) che desiderano guadagnare da prove.

Answer 2

Uniform complessità prova è un campo dedicato (tra gli altri) allo studio delle nozioni costruttive delle prove, e la loro relazione con classi di complessità. Per ciascuna delle popolari (uniforme) classi circuito complessità, si può definire una teoria in cui tutto ciò che è dimostrabile ha un "supporto" in un algoritmo in questa classe di complessità. algoritmi randomizzati sono alloggiati attraverso versioni del principio dei cassetti (stranamente).

Purtroppo io non sono un esperto, quindi non posso dire molto di più, altro che si punti al libro di Cook e Nguyen (lo stesso Cook come nel teorema di Cook) e al lavoro di Emil Jerábek , soprattutto il suo tesi sul calcolo randomizzato.