P (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, P, còn được gọi là PTIME hoặc DTIME${\displaystyle (n^{O(1)})}$, là một trong những lớp cơ bản nhất trong các lớp độ phức tạp tính toán. Nó bao gồm tất cả các bài toán quyết định có thể được giải quyết bằng một máy Turing tất định trong thời gian đa thức.

Luận đề Cobham khẳng định rằng P là lớp các bài toán "có thể giải quyết hiệu quả"^[1]. Trên thực tế, có một số bài toán chưa biết có trong P hay không nhưng đã có thuật toán thực tiễn, trong khi một số bài toán trong P vẫn chưa có. Mặc dù vậy đây vẫn là một quy tắc hữu ích.

Định nghĩa

Một ngôn ngữ L là trong P nếu và chỉ nếu tồn tại một máy Turing tất định M sao cho

• Thời gian chạy của M là một đa thức của độ dài dữ liệu vào
• Đối với tất cả x trong L, M cho kết quả 1
• Đối với tất cả x không có trong L, M cho kết quả 0

Các bài toán nổi bật trong P

P bao gồm nhiều bài toán phổ biến, chẳng hạn như phiên bản quyết định của quy hoạch tuyến tính, tính ước số chung lớn nhất, tìm cặp ghép cực đại, xác định xem một số có phải số nguyên tố hay không^[2].

Quan hệ với các lớp khác

P là một tập hợp con của NP (tập hợp các bài toán giải được trong thời gian đa thức bởi máy Turing bất định). Mặc dù chưa được chứng minh, nhiều chuyên gia tin rằng P là tập con thực sự của NP.

P bao hàm NL, lớp các bài toán giải được trong không gian bộ nhớ ${\displaystyle O(\log n)}$ bởi máy Turing bất định.

Ghi chú

1. Cobham, Alan (1965). “The intrinsic computational difficulty of functions”. Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
2. Manindra Agrawal, Neeraj Kayal, Nitin Saxena. “PRIMES is in P” (PDF). Annals of Mathematics 160 (2004), no. 2, pp. 781–793.