1221737
ZPP (độ phức tạp)
https://vi.wikipedia.org/wiki?curid=1221737
Title: ZPP (độ phức tạp)
Trong lý thuyết độ phức tạp tính toán, ZPP (viết tắt của zero-error probabilistic polynomial time - thời gian đa thức với xác suất sai bằng không) là lớp độ phức tạp bao gồm các bài toán sao cho tồn tại máy Turing ngẫu nhiên với các tính chất sau:
Nói cách khác, thuật toán được phép sử dụng các lần tung đồng xu ngẫu nhiên/bit ngẫu nhiên. Kết quả của thuật toán luôn chính xác. Các thuật toán như vậy gọi là thuật toán Las Vegas. Với bài toán có kích thước "n", tồn tại đa thức "p"("n") sao cho thời gian chạy trung bình luôn nhỏ hơn "p"("n") cho mọi dữ liệu vào. Tuy nhiên, với một số bộ giá trị của các bit ngẫu nhiên, thuật toán có thể chạy chậm hơn rất nhiều.
Một định nghĩa khác của ZPP là lớp các bài toán có máy Turing thỏa mãn các tính chất sau:
Hai định nghĩa trên là tương đương.
ZPP được định nghĩa dựa trên máy Turing ngẫu nhiên. Máy này cũng được dùng để định nghĩa các lớp khác như BPP và RP. Lớp BQP được định nghĩa dựa trên máy tính lượng tử ngẫu nhiên.
Định nghĩa theo giao của hai lớp.
Lớp ZPP đúng bằng giao của hai lớp RP và Co-RP. Đây là một định nghĩa khác của ZPP. Để thấy định nghĩa này tương đương với các định nghĩa trên, có thể nhận thấy mọi bài toán nằm trong "cả" RP và co-RP đều có một thuật toán Las Vegas như sau:
Với mọi dữ liệu vào, chỉ một trong hai thuật toán A và B có thể trả lời sai, và xác suất sai là không quá 50%. Vì vậy xác suất cần thực hiện "k" lần lặp giảm theo hàm mũ của "k". Do đó giá trị kì vọng của thời gian chạy là đa thức. Như vậy giao của RP và co-RP nằm trong ZPP.
Để chứng minh ZPP nằm trong giao của RP và co-RP, giả sử ta có một thuật toán Las Vegas C giải quyết được một bài toán trong ZPP. Có một thuật toán RP cho bài toán đó như sau: