P (mức độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, P, hay còn gọi là PTIME hoặc DTIME$\left(n^{O\left(1\right)}\right)$, là một trong những lớp căn bản nhất trong lý thuyết độ 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ởi một máy Turing xác định trong thời gian đa thức.

Luận đề Cobham cho rằng P là tập hợp các bài toán 'có thể giải quyết một cách hiệu quả'. Thực tế, một số bài toán chưa rõ có nằm trong P hay không, mặc dù đã có thuật toán thực tế, trong khi một số bài toán trong P vẫn chưa được giải quyết. Dù vậy, quy tắc này vẫn rất hữu ích.

Khái niệm

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

• Thời gian thực hiện của M là một đa thức theo độ dài của dữ liệu đầu vào
• Đối với mọi x thuộc L, M trả về giá trị 1
• Đối với mọi x không thuộc L, M trả về giá trị 0

Các bài toán tiêu biểu trong P

P chứa nhiều bài toán nổi bật, chẳng hạn như bài toán quyết định của quy hoạch tuyến tính, tính toán ước số chung lớn nhất, tìm cặp ghép tối đa, và xác định tính nguyên tố của một số.

Liên 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 có thể giải trong thời gian đa thức bằng máy Turing không xác định). Mặc dù chưa có chứng minh rõ ràng, nhiều nhà nghiên cứu cho rằng P thực sự là tập hợp con của NP.

Tập hợp các bài toán có thể giải trong không gian bộ nhớ $O(\log <!--\; \; -->n)$ bởi máy Turing không xác định.

Chú thích