Tôi đang cố gắng đọc chương 4 của Foundation of Cryptography của Oded Goldreich (chỉ để bạn "điều chỉnh" câu trả lời của mình, tôi có nền tảng kỹ thuật).
Nếu tôi hiểu chính xác, hãy đưa ra một trình giả lập hoàn hảo $S_1$ khả năng tạm dừng không phải là vấn đề vì chúng tôi có thể xác định trình giả lập $S_2$ mà lặp đi lặp lại $S_1$ hãy cùng nói nào $n$ lần, xuất ra kết quả của lần không dừng đầu tiên $S_1$ lặp lại hoặc kết quả "giả" nếu TẤT CẢ $S_1$ lặp lại dừng lại. Bằng cách này, xác suất của $S_2$ xuất ra kết quả giả có thể được hạ xuống tùy thích với sự tăng trưởng của $n$.
$S_1$ xác suất dừng được giới hạn ở trên bởi $1/2$, nhưng tại sao? Dường như với tôi rằng mỗi $S_1$ xác suất dừng $<1$ sẽ được hạ thấp về phía $0$ đủ lớn $n$. Hơn nữa, trình mô phỏng dường như là một đối số rất khác với xác suất đầy đủ/đúng đắn, trong đó nghiêm ngặt $1/2$ ngưỡng được chứng minh bằng quy tắc đa số được áp dụng cho chiến lược lặp lại (khác nhau) đó.
Và, btw, có lý do nào để chọn $S_1$ giá trị lặp lại $n$ giống như số lần lặp lại khác cần thiết để chuyển từ mức độ đầy đủ/đầy đủ yếu sang mức độ mạnh hơn? Hay là số lượng của hai loại lặp lại độc lập lẫn nhau? Tôi đoán nghi ngờ này xuất phát từ việc tôi bối rối về việc nếu $S_2$ là trình giả lập cho IP yếu hoặc cho IP mạnh hơn ...
Cảm ơn!
