derandomize một thuật toán BPP

Question

Giả sử chúng ta có một thuật toán BPP $A$ st thời gian chạy của nó là ngẫu nhiên và là $O(n^2)$Trong kỳ vọng. Làm cách nào để chúng tôi tạo một thuật toán BPP mới$B$ để giải quyết cùng một vấn đề vì nó có thời gian chạy xác định $O(n^2)$?

Nỗ lực của tôi: Biểu thị thời gian chạy của $A$ như $T$. Giả sử$E(T)\leq T(n)=O(n^2)$.

1. Chạy $A$ nhất $kT(n)$ các bước.
2. Nếu nó kết thúc, hãy trả lại đầu ra của nó; nếu không, đầu ra Có với xác suất$q$.

Nhưng tôi vừa chứng minh rằng đây không thể là thuật toán BPP cho bất kỳ $q$... Bất kỳ gợi ý xin vui lòng?

Answer 1

Derandomization là quá trình trong đó một thuật toán ngẫu nhiên được chuyển đổi thành một thuật toán xác định tương đương. Đây không phải là điều mà bài tập này yêu cầu bạn làm. Thuật toán$B$ vẫn là ngẫu nhiên - chỉ có thời gian chạy của nó là xác định.

Giả sử rằng $A$ quyết định vấn đề $L$, theo nghĩa sau: nếu $x \in L$ sau đó $\Pr[A(x) = 1] \geq 2/3$, và nếu $x \notin L$ sau đó $\Pr[A(x) = 0] \geq 2/3$. Hơn nữa, có một chức năng$f(n) = O(n^2)$ sao cho thời gian chạy dự kiến ​​là $A$ trên $x$ luôn luôn là nhiều nhất $f(|x|)$. Chúng tôi muốn xây dựng một thuật toán mới$B$ với cùng một hành vi liên quan đến $L$và với thuộc tính bổ sung sau: có một chức năng $g(n) = O(n^2)$ sao cho thời gian chạy của $B$ trên $x$chính xác là $g(|x|)$.

Giả sử rằng $f(n) = Cn^2$và xem xét giải pháp của bạn với $K = 3C$ và $q=1/2$. Nếu chúng ta cẩn thận, thì sẽ tồn tại một hàm$g(n) = O(n^2)$ sao cho thời gian chạy của $B$ trên $x$ chính xác $g(|x|)$. Còn tài sản kia thì sao?

Giả sử rằng $x \in L$ có kích thước $|x|=n$. Thời gian chạy dự kiến ​​của$A$ trên $x$ nhiều nhất là $f(n) = Cn^2$, và vì thế $A$ chấm dứt trong $Kn^2$ các bước có xác suất $p \geq 2/3$. Nếu điều này xảy ra, xác suất$B$ đầu ra $1$ là ít nhất $2/3$. Nếu không, xác suất$B$ đầu ra $1$ Là $1/2$. Tổng cộng,$$\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}.$$ Tương tự, nếu $x \notin L$ sau đó $\Pr[B(x) = 0] \geq 11/18$. Đây gần như là những gì chúng tôi muốn - chúng tôi muốn$11/18$ được thay thế bởi $2/3$.

Để nâng cao xác suất thành công ("giảm lỗi"), chúng tôi cần chạy $A$nhiều lần và chiếm đa số phiếu. Bằng cách chạy$A$ đủ lần và bằng cách tăng giá trị của $K$, chúng tôi nhận được xác suất lỗi là $B$xuống bất kỳ hằng số dương nào. Thông tin chi tiết còn lại cho bạn.