BPP (độ phức tạp)

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⁻ᶜ hoặc nhỏ hơn 2⁻ⁿᶜ, 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. 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ố.

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.
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.
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. 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ᴬ = BPPᴬ và Pᴮ ≠ BPPᴮ. 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.

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 = . 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ᴾᴴ) 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 đó , có độ phức tạp mạch  thì P = BPP.