Trong lý thuyết độ phức tạp tính toán, P, còn được gọi là PTIME hoặc DTIME
(
n
O
(
1
)
)
{\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ả". 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.