1221737
ZPP (độ phức tạp)
https://vi.wikipedia.org/wiki?curid=1221737
Title: ZPP (độ phức tạp)
Theo bất đẳng thức Markov, xác suất C kết thúc trước khi ta dừng C là ít nhất 1/2. Do đó khi câu trả lời đúng là CÓ, xác suất thuật toán dừng C và trả về KHÔNG chỉ là 1/2 đúng như yêu cầu của thuật toán RP. Thuật toán co-RP cũng tương tự như vậy, điểm khác biệt duy nhất là nó trả về CÓ khi phải dừng C.
Chứng minh và bằng chứng.
Có thể định nghĩa các lớp NP, RP và ZPP thông qua khái niệm chứng minh một xâu là phần tử của một tập hợp.
Định nghĩa: Một "thuật toán kiểm chứng" V cho tập hợp X là một máy Turing thỏa mãn điều kiện sau:
Có thể coi xâu "w" là một "bằng chứng" cho việc "x" thuộc "X".
Các lớp NP, RP và ZPP bao gồm các tập hợp có bằng chứng cho việc kiểm tra thành viên. Lớp NP chỉ yêu cầu tồn tại bằng chứng. Bằng chứng có thể rất hiếm. Trong số 2f(|x|) xâu độ dài f(|x|), với f() là một đa thức, chỉ cần tồn tại ít nhất một xâu khiến cho thuật toán kiểm chứng chấp nhận (nếu x thuộc X. Nếu x không thuộc X, không xâu nào có thể khiến thuật toán kiểm chứng chấp nhận).
Với các lớp RP và ZPP, đa số các xâu trong số 2f(|x|) xâu đều là bằng chứng.
Các lớp phần bù tương ứng gồm các tập hợp có bằng chứng cho việc không thuộc tập hợp. Chẳng hạn, co-RP là lớp gồm các tập hợp X sao cho, nếu x không thuộc X, đa số các xâu được chọn ngẫu nhiên đều là bằng chứng cho việc x không thuộc X. ZPP là lớp gồm các tập hợp sao cho với mọi x, đa số các xâu ngẫu nhiên đều là bằng chứng, hoặc cho việc x thuộc X, hoặc cho việc x không thuộc X, tùy theo x có thuộc X hay không.