RP (độ phức tạp)
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
Trong lý thuyết độ phức tạp tính toán, RP (viết tắt của "randomized polynomial time") 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:
| Thuật toán RP (lặp 1 lần) | ||
|---|---|---|
| Lời giải thu được | ||
| Lời giải đúng |
Có | Không |
| Có | ≥ 1/2 | ≤ 1/2 |
| Không | 0 | 1 |
| Thuật toán RP(lặp n lần) | ||
| Lời giải thu được | ||
| Lời giải đúng |
Có | Không |
| Có | ≥ 1 − 2−n | ≤ 2−n |
| Không | 0 | 1 |
| Thuật toán co-RP (lặp 1 lần) | ||
| Lời giải thu được | ||
| Lời giải đúng |
Có | Không |
| Có | 1 | 0 |
| Không | ≤ 1/2 | ≥ 1/2 |
- Luôn chạy trong thời gian đa thức của độ dài dữ liệu vào
- Nếu lời giải đúng là Không thì máy luôn trả về Không
- Nếu lời giải đúng là Có, thì máy trả về Có với xác suất ít nhất 1/2.
Nói cách khác, thuật toán cho các bài toán trong RP được phép dùng bit ngẫu nhiên trong quá trình thực thi. Trường hợp duy nhất thuật toán trả về Có là khi lời giải đúng là Có. Tuy nhiên khi thuật toán trả về Không, lời giải đúng có thể là Có hoặc Không.
Nếu lời giải đúng là Có thì nếu thực hiện thuật toán n lần độc lập nhau, thì nó trả về Có ít nhất một lần với xác suất ít nhất 1 − 2−n.
Trong định nghĩa, số 1/2 được chọn tùy ý. Tập hợp RP không thay đổi nếu 1/2 được thay bằng bất kì hằng số nào nhỏ hơn 1 (hằng số ở đây nghĩa là không phụ thuộc kích thước dữ liệu vào).
Liên hệ với các lớp độ phức tạp khác sửa
Theo định nghĩa, với mọi bài toán trong RP, tồn tại thuật toán sao cho nếu lời giải trả về là Có thì thuật toán luôn đúng và nếu lời giải trả về là Không thì thuật toán thường đúng. Lớp co-RP được định nghĩa tương tự như vậy, nhưng với các thuật toán co-RP, lời giải Không luôn đúng và lời giải Có thường đúng. Nói cách khác, thuật toán chấp nhận mọi trường hợp Có nhưng có thể chấp nhận hoặc từ chối các trường hợp Không. Lớp BPP gồm các bài toán có thuật toán thường đúng nhưng được phép trả lời sai với xác suất thấp trong cả hai trường hợp, và do đó là tập hợp cha của cả RP và co-RP. Giao của RP và co-RP là lớp ZPP.
Liên hệ với P và NP sửa
 |
Vấn đề mở trong khoa học máy tính: Có phải P = RP ? (các vấn đề mở khác trong khoa học máy tính)
|
P là tập hợp con của RP, và RP là tập hợp con của NP. Tương tự như vậy, P là tập hợp con của co-RP và co-RP là tập hợp con của co-NP. Hiện chưa biết các mối quan hệ tập hợp cha-con đó có chặt hay không. Tuy nhiên nếu giả thuyết phổ biến P = BPP là đúng thì RP, co-RP, và P đều bằng nhau.
Một ví dụ quan trọng của co-RP hiện vẫn chưa biết có nằm trong P không là kiểm tra đa thức không yêu cầu xác định xem một đa thức cho trước có đồng nhất bằng đa thức không hay không. Ví dụ, x·x − y·y − (x + y)·(x − y) là đa thức không trong khi x·x + y·y không phải.
Một định nghĩa khác của RP là lớp các bài toán giải được bằng máy Turing không đơn định trong đó máy chấp nhận khi và chỉ khi tỉ lệ số đường tính toán chấp nhận là ít nhất một hằng số. Trong khi đó, với lớp NP, máy chấp nhận khi có ít nhất một đường tính toán chấp nhận. Vì vậy RP rõ ràng là tập hợp con của NP.
Xem thêm sửa
Tham khảo sửa
Sipser, Michael (2012). Introduction to the Theory of Computation (ấn bản 3). Course Technology Inc. ISBN 113318779X.