BPP (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, BPP (viết tắt của cụm từ tiếng Anh bounded-error probabilistic polynomial) là lớp các bài toán quyết định giải được bằng máy Turing ngẫu nhiên trong thời gian đa thức, với xác suất sai không quá 1/3 cho mọi trường hợp.

Thuật toán BPP(lặp 1 lần)
	Lời giải thu được
Lời giải đúng	Có	Không
Có	≥ 2/3	≤ 1/3
Không	≤ 1/3	≥ 2/3
Thuật toán BPP(lặp k lần)
	Lời giải thu được
Lời giải đúng	Có	Không
Có	> 1 − 2^−ck	< 2^−ck
Không	< 2^−ck	> 1 − 2^−ck
với hằng số c > 0

Một bài toán nằm trong lớp BPP nếu có thuật toán cho nó thỏa mãn các tính chất sau:

• Thuật toán được phép sử dụng lựa chọn ngẫu nhiên
• Thuật toán chạy trong thời gian đa thức
• Với mọi trường hợp, bất kể lời giải đúng là Có hay Không, thuật toán có xác suất trả lời sai không quá 1/3.

Giới thiệu

BPP là một trong những lớp lớn nhất của các bài toán thực tiễn, nghĩa là đa số các bài toán được quan tâm trong BPP đều có thuật toán ngẫu nhiên có thể thực thi nhanh chóng trên máy tính. Do đó, một hướng nghiên cứu quan trọng là xác định xem một bài toán hay một lớp các bài toán có nằm trong BPP. BPP chứa P là tập hợp các bài toán giải được trong thời gian đa thức trên máy Turing đơn định do máy Turing đơn định là trường hợp đặc biệt của máy Turing ngẫu nhiên.

Cho một bài toán thực tế, xác suất sai bằng 1/3 có thể là quá lớn, nhưng lựa chọn 1/3 trong định nghĩa là tùy ý. Nó có thể là bất kì một hằng số nào lớn hơn 0 và nhỏ hơn 1/2, và tập hợp BPP là không thay đổi. Nó thậm chí không cần là hằng số: lớp BPP là không đổi dù cho phép xác suất sai lên tới 1/2 − n^−c hoặc nhỏ hơn 2^−nc, trong đó c là hằng số nguyên bất kì, và n là kích thước dữ liệu vào. Ý tưởng chính là tuy mỗi lần thực thi thuật toán có thể có xác suất sai cao, nếu lặp lại nhiều lần thì xác suất đa số các lần thực thi là sai giảm theo hàm lũy thừa theo chặn Chernoff.^[1] Do đó có thể thu được thuật toán với xác suất sai thấp bằng cách lặp đi lặp lại thuật toán cơ sở nhiều lần và chọn lời giải đa số.

Định nghĩa

Ngôn ngữ L nằm trong BPP nếu tồn tại máy Turing ngẫu nhiên M thỏa mãn

• M chạy trong thời gian đa thức
• Với mọi x trong L, M trả lời 1 với xác suất ít nhất 2/3
• Với mọi x không trong L, M trả lời 1 với xác suất không quá 1/3

Không như lớp ZPP, máy M bắt buộc phải chạy trong thời gian đa thức, bất kể các lựa chọn ngẫu nhiên là thế nào.

Ngoài ra, BPP cũng có thể được định nghĩa bằng máy Turing đơn định. Ngôn ngữ L nằm trong BPP nếu tồn tại đa thức p và máy Turing đơn định M, sao cho

• M chạy trong thời gian đa thức
• Với mọi x trong L, tỉ lệ số xâu y độ dài p(|x|) thỏa mãn M(x,y) = 1 là ít nhất 2/3
• Với mọi x không trong L, tỉ lệ số xâu y độ dài p(|x|) thỏa mãn M(x,y) = 1 là không quá 1/3

Trong định nghĩa thứ hai, y tương ứng với các lựa chọn ngẫu nhiên của thuật toán.

Các bài toán liên quan

Vấn đề mở trong khoa học máy tính: Có phải P = BPP ? (các vấn đề mở khác trong khoa học máy tính)

Bên cạnh các bài toán trong P, và do đó trong BPP, có nhiều bài toán trong BPP nhưng không biết có nằm trong P hay không. Số bài toán như vậy ngày càng giảm và người ta giả thuyết rằng P = BPP.

Trong một thời gian dài, một bài toán nổi tiếng trong BPP nhưng không biết có nằm trong P hay không là kiểm tra một số cho trước có phải số nguyên tố hay không. Tuy nhiên, trong bài báo năm 2002 mang tên PRIMES is in P, Manindra Agrawal và các học trò Neeraj Kayal và Nitin Saxena tìm ra một thuật toán đơn định cho nó, và do đó chứng minh nó nằm trong P.

Một bài toán quan trọng trong BPP (thực ra là trong co-RP) vẫn chưa biết có nằm trong P hay không là kiểm tra đa thức bằng không: kiểm tra xem một đa thức cho trước có bằng đa thức không hay không. Nói cách khác là xác định liệu có cách gán giá trị cho các biến sao cho giá trị đa thức là khác không. Có thuật toán ngẫu nhiên như sau: thử d bộ giá trị ngẫu nhiên cho các biến và xem đa thức có khác không tại một trong số các giá trị này hay không, trong đó d là bậc của đa thức.^[2]

Các lớp liên quan

Nếu loại đi khả năng dùng lựa chọn ngẫu nhiên của BPP, ta thu được lớp P. Trong định nghĩa, nếu thay máy Turing bằng máy tính lượng tử, ta thu được lớp BQP.

Thuật toán Monte Carlo là thuật toán ngẫu nhiên thường cho câu trả lời chính xác. Các bài toán trong BPP có thuật toán Monte Carlo chạy trong thời gian đa thức. Ngoài ra, có thuật toán Las Vegas là thuật toán luôn đưa ra câu trả lời chính xác nhưng có thể "thất bại" trong việc tìm ra câu trả lời với xác suất thấp. Các thuật toán Las Vegas với thời gian kì vọng đa thức tạo thành lớp ZPP. Nói cách khác, ZPP bao gồm các bài toán có thuật toán ngẫu nhiên luôn cho câu trả lời chính xác và thời gian kì vọng đa thức. Điều kiện thời gian kì vọng đa thức là yếu hơn điều kiện thời gian đa thức do thuật toán có thể có thời gian chạy lũy thừa, nhưng với xác suất rất thấp.

Các tính chất độ phức tạp tính toán

BPP là đóng với phép lấy phần bù; nghĩa là, BPP = co-BPP. BPP là thấp cho chính nó, nghĩa là một máy BPP với khả năng giải quyết bài toán BPP ngay tức thì (một máy tiên tri BPP) không mạnh hơn phiên bản thông thường. Nghĩa là, BPP^BPP = BPP.

Mối liên hệ giữa BPP và NP là không rõ: chưa biết liệu BPP có là tập hợp con của NP, NP có là tập hợp con của BPP hay chúng không thể so sánh được. Nếu NP nằm trong BPP (thường được coi là khó có thể xảy ra do nó dẫn đến thuật toán hiệu quả cho các bài toán NP-đầy đủ), thì NP = RP và PH ⊆ BPP.^[3]

RP là tập hợp con của BPP, và BPP là tập hợp con của PP. Hiện vẫn chưa biết liệu hai mối quan hệ tập hợp cha-con đó có chặt hay không. Ngay cả việc P có là tập hợp con thực sự của PSPACE vẫn chưa được chứng minh. BPP nằm trong tầng thứ hai của cấp bậc đa thức và do đó nằm trong PH. Cụ thể hơn, định lý Sipser–Lautemann phát biểu rằng BPP ⊆ Σ₂ ∩ Π₂. Do đó, P = NP dẫn tới P = BPP do trong trường hợp này, PH bằng P. Vì vậy, hoặc P = BPP hoặc P ≠ NP hoặc cả hai.

Định lý Adleman phát biểu rằng mọi ngôn ngữ trong BPP đều có thể quyết định bởi một gia đình các mạch lôgic Bool, nghĩa là BPP nằm trong P/poly.^[4] Thực vậy, mọi thuật toán BPP cho dữ liệu vào có độ dài cố định đều có thể được chuyển thành đơn định bằng cách dùng một chuỗi bit ngẫu nhiên cố định. Tuy nhiên, việc tìm ra chuỗi đó có thể rất khó.

Tồn tại hai máy tiên tri A và B, sao cho P^A = BPP^A và P^B ≠ BPP^B. Hơn nữa đối với máy tiên tri ngẫu nhiên với xác suất 1, P = BPP và BPP nằm trong NP và co-NP.^[5]

Khử ngẫu nhiên

Đa số các chuyên gia đều tin vào việc tồn tại máy sinh số giả ngẫu nhiên mạnh. Theo giả thuyết này, việc sử dụng lựa chọn ngẫu nhiên không làm tính toán trong thời gian đa thức mạnh lên, nghĩa là P = RP = BPP. Tuy nhiên, các máy sinh số ngẫu nhiên được biết đến hiện nay không đủ để suy ra kết quả này.

László Babai, Lance Fortnow, Noam Nisan, và Avi Wigderson chứng minh rằng trừ phi EXPTIME bằng MA, BPP nằm trong i.o.-SUBEXP = ${\displaystyle \bigcap _{\varepsilon >0}{\hbox{i.o.-DTIME}}(2^{n^{\varepsilon }})}$.^[6] Lớp i.o.-SUBEXP (viết tắt của cụm từ tiếng Anh infinitely often SUBEXP), bao gồm các bài toán có thuật toán thời gian nhỏ hơn hàm mũ cho vô hạn các kích thước dữ liệu vào. Họ cũng chứng minh rằng P = BPP nếu cấp bậc hàm mũ (định nghĩa theo cấp bậc đa thức và E là E^PH) bằng E. Tuy nhiên, người ta thường giả thuyết rằng cấp bậc thời gian hàm mũ không bằng E.

Russell Impagliazzo và Avi Wigderson chứng minh rằng nếu tồn tại một bài toán trong E, trong đó ${\displaystyle {\textrm {E}}={\textrm {DTIME}}\left(2^{O(n)}\right)}$, có độ phức tạp mạch ${\displaystyle 2^{\Omega (n)}}$ thì P = BPP.^[7]

Tham khảo

1. [1]
2. Madhu Sudan và Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: Bài 6: Thuật toán ngẫu nhiên, các tính chất của BPP. 26 tháng 2 năm 2003.
3. [2]
4. Adleman, L. M. (1978). “Two theorems on random polynomial time”. Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing. tr. 75–83.
5. Bennett, Charles H.; Gill, John (1981), “Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1”, SIAM Journal on Computing, 10 (1): 96–113, ISSN 1095-7111
6. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs". Computational Complexity, 3:307–318.
7. Russell Impagliazzo and Avi Wigderson (1997). "P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229. doi:10.1145/258533.258590

• Valentine Kabanets (2003). "CMPT 710 – Lý thuyết độ phức tạp: Bài 16". Đại học Simon Fraser.
• Christos Papadimitriou (1993). Computational Complexity (ấn bản thứ 1). Addison Wesley. ISBN 0-201-53082-1. Trang 257–259 của phần 11.3: Nguồn ngẫu nhiên. Trang 269–271 của phần 11.4: Độ phức tạp mạch.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Phần 10.2.1: Lớp BPP, tr. 336–339.

Liên kết ngoài

• Princeton CS 597E: Danh sách các bài báo khử ngẫu nhiên
• Harvard CS 225: Giả ngẫu nhiên Lưu trữ 2003-08-05 tại Wayback Machine