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.

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−*n<sup>c</sup>*, 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ố.

## Đị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

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 * [[thuật toán AKS|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.

## 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 (độ phức tạ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 (độ phức tạp)|NP]]** là không rõ: chưa biết liệu **BPP** có là tập hợp con của **[[NP (độ phức tạp)|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 (độ phức tạp)|PH]]** ⊆ **BPP**.

**[[RP (độ phức tạp)|RP]]** là tập hợp con của **BPP**, và **BPP** là tập hợp con của **[[PP (độ phức tạp)|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** ⊆ Σ2 ∩ Π2. 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**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**.

## 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 (độ phức tạp)|MA]]**, **BPP** nằm trong **i.o.-SUBEXP** = \bigcap_{\varepsilon>0}\hbox{i.o.-DTIME}(2^{n^\varepsilon}). 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<sup>PH</sup>**) 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 (complexity)|E]]**, trong đó \textrm{E}=\textrm{DTIME} \left(2^{O(n)} \right), có độ phức tạp mạch 2^{\Omega(n)} thì **P** = **BPP**.

## Tham khảo

* Valentine Kabanets (2003). "CMPT 710 – Lý thuyết độ phức tạp: Bài 16". Đại học Simon Fraser.
*  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.
*  Phần 10.2.1: Lớp BPP, tr.&nbsp;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