1221737
ZPP (độ phức tạp)
https://vi.wikipedia.org/wiki?curid=1221737
Title: ZPP (độ phức tạp)
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.