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:

• Máy luôn trả lời đúng CÓ hoặc KHÔNG.
• Với mọi dữ liệu vào, giá trị kì vọng của thời gian chạy luôn là đa thức.

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:

• Luôn chạy trong thời gian đa thức.
• Luôn trả lời CÓ, KHÔNG hoặc KHÔNG BIẾT.
• Nếu máy trả lời CÓ hoặc KHÔNG thì đó là câu trả lời đúng.
• Nếu câu trả lời đúng là CÓ, thì máy trả về CÓ với xác suất ít nhất 1/2 (và KHÔNG BIẾT trong trường hợp còn lại).
• Nếu câu trả lời đúng là KHÔNG, thì máy trả về KHÔNG với xác suất ít nhất 1/2 (và KHÔNG BIẾT trong trường hợp còn lại).

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:

• Xét ngôn ngữ L được thừa nhận bởi thuật toán RP A và thuật toán co-RP B (có thể hoàn toàn khác A).
• Với mọi dữ liệu vào, trước tiên thực hiện A. Nếu A trả về CÓ, thì câu trả lời đúng nhất định là CÓ. Nếu không thì chạy B trên dữ liệu vào. Nếu B trả về KHÔNG, thì câu trả lời đúng nhất định là KHÔNG. Nếu cả hai trường hợp đều không xảy ra thì lặp lại bước này.

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:

• Chạy C trong số bước lớn hơn 2 lần giá trị kì vọng của thời gian chạy của C. Nếu C kết thúc thì trả về kết quả của C. Nếu C chưa kết thúc thì trả về KHÔNG.

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:

• Nếu x thuộc X thì tồn tại xâu w sao cho V(x,w) chấp nhận.
• Nếu x không thuộc X, thì với mọi xâu w, V(x,w) đều từ chối.

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ố 2^f(|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ố 2^f(|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.

Có thể dễ dàng liên hệ định nghĩa này với các định nghĩa khác của RP, co-RP và ZPP. Máy Turing ngẫu nhiên V^*_w(x) ứng với máy Turing đơn định V(x,w) sau khi thay băng chứa các bit ngẫu nhiên V^* bằng một băng dữ liệu vào thứ hai cho V trên đó có chứa xâu bằng chứng. Bằng cách chọn xâu bằng chứng một cách ngẫu nhiên, thuật toán kiểm chứng là một máy Turing ngẫu nhiên chấp nhận x nếu x thuộc X với xác suất cao (ít nhất 1/2), nhưng luôn từ chối nếu x không thuộc X (cho RP); từ chối x nếu x không thuộc X với xác suất cao nhưng luôn chấp nhận nếu x thuộc X (cho co-RP); và quyết định đúng x có thuộc X hay không với xác suất cao, nhưng không bao giờ quyết định sai (cho ZPP).

Bằng cách lặp đi lặp lại việc tìm bằng chứng, ta thu được một thuật toán quyết định việc x có thuộc X trong thời gian kì vọng đa thức. Ngược lại, nếu có một thuật toán có thời gian kì vọng đa thức (với mọi x), thì với xác suất cao, thời gian chạy là đa thức. Dãy các bit ngẫu nhiên trong các trường hợp đó chính là các bằng chứng.

Có thể so sánh ZPP với BPP. Lớp BPP không đòi hỏi bằng chứng, nhưng việc có bằng chứng là điều kiện đủ (nên BPP chứa RP, co-RP và ZPP). Với mỗi ngôn ngữ BPP, đều có một thuật toán kiểm chứng V(x,w) chấp nhận x nếu x thuộc X cho ít nhất 2/3 các xâu w, và từ chối x nếu x không thuộc X cho ít nhất 2/3 các xâu w.

Liên hệ với các lớp khác

Vì ZPP = RP ∩ coRP, ZPP nằm trong cả RP và coRP.

Lớp P nằm trong ZPP, và nhiều người giả thuyết rằng P = ZPP, nghĩa là, mọi thuật toán Las Vegas đều có thuật toán tương đương không ngẫu nhiên chạy trong thời gian đa thức.

Tham khảo

• Arora, Sanjeev; Barak, Boaz, Computational Complexity: A Modern Approach (ấn bản thứ 1), tr. 131, ISBN 978-0521424264

Liên kết ngoài

• Bản mẫu:CZoo