BPP algoritmasını derandomize etme

Question

Bir BPP algoritmamız olduğunu varsayalım $A$ çalışma süresi rastgele ve $O(n^2)$beklenti içinde. Yeni bir BPP algoritmasını nasıl oluştururuz$B$ aynı problemi çözmek için belirleyici çalışma süresine sahiptir $O(n^2)$?

Çabam: çalışma süresini belirtin $A$ gibi $T$. Varsayalım$E(T)\leq T(n)=O(n^2)$.

1. Çalıştırmak $A$ en çok $kT(n)$ adımlar.
2. Sonlanırsa, çıktısını döndürün; aksi takdirde, olasılıkla Evet çıktısı$q$.

Ancak bunun herhangi biri için bir BPP algoritması olamayacağını kanıtladım. $q$... Herhangi bir ipucu lütfen?

Answer 1

Derandomizasyon, rastgele bir algoritmanın eşdeğer bir deterministik algoritmaya dönüştürüldüğü süreçtir. Bu egzersizin sizden yapmanızı istediği şey bu değil . Algoritma$B$ hala randomize - yalnızca çalışma süresi deterministiktir.

Farz et ki $A$ soruna karar verir $L$şu anlamda: eğer $x \in L$ sonra $\Pr[A(x) = 1] \geq 2/3$, ve eğer $x \notin L$ sonra $\Pr[A(x) = 0] \geq 2/3$. Dahası, bir işlev var$f(n) = O(n^2)$ öyle ki beklenen çalışma süresi $A$ açık $x$ her zaman en fazla $f(|x|)$. Yeni bir algoritma oluşturmak istiyoruz$B$ aynı davranışla $L$ve aşağıdaki ek özellik ile: bir işlev var $g(n) = O(n^2)$ öyle ki çalışma süresi $B$ açık $x$olduğunu tam olarak $g(|x|)$.

Farz et ki $f(n) = Cn^2$ve çözümünüzü düşünün $K = 3C$ ve $q=1/2$. Dikkatli olursak, bir işlev olacaktır.$g(n) = O(n^2)$ öyle ki çalışma süresi $B$ açık $x$ tam olarak $g(|x|)$. Peki ya diğer mülk?

Farz et ki $x \in L$ boyuta sahip $|x|=n$. Beklenen çalışma süresi$A$ açık $x$ en fazla $f(n) = Cn^2$, ve bu yüzden $A$ içinde sona erer $Kn^2$ olasılıklı adımlar $p \geq 2/3$. Bu olursa, olasılık$B$ çıktılar $1$ en azından $2/3$. Aksi takdirde,$B$ çıktılar $1$ dır-dir $1/2$. Toplamda,$$\Pr[B(x) = 1] \geq p \cdot \frac{2}{3} + (1-p) \cdot \frac{1}{2} = \frac{1}{2} + p \cdot \frac{1}{6} \geq \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{6} = \frac{11}{18} > \frac{1}{2}.$$ Benzer şekilde, if $x \notin L$ sonra $\Pr[B(x) = 0] \geq 11/18$. Bu neredeyse istediğimiz şey - istiyoruz$11/18$ ile değiştirilecek $2/3$.

Başarı olasılığını artırmak için ("hata azaltma"), $A$birkaç kez ve çoğunluk oyu alır. Koşarak$A$ yeterince kez ve değerini artırarak $K$hata olasılığını alıyoruz $B$herhangi bir pozitif sabite kadar. Detaylar size bırakıldı.