p là gì trong toán học

Bách khoa toàn thư banh Wikipedia

Bạn đang xem: p là gì trong toán học

Trong lý thuyết chừng phức tạp đo lường, P, còn được gọi là PTIME hoặc DTIME, là 1 trong trong mỗi lớp cơ bạn dạng nhất trong những lớp chừng phức tạp đo lường. Nó bao hàm toàn bộ những câu hỏi ra quyết định rất có thể được giải quyết và xử lý vì chưng một máy Turing vớ lăm le vô thời hạn nhiều thức.

Luận đề Cobham xác minh rằng P.. là lớp những câu hỏi "có thể giải quyết và xử lý hiệu quả"^[1]. Trên thực tiễn, sở hữu một trong những câu hỏi không biết sở hữu vô P.. hay là không tuy nhiên đang được sở hữu thuật toán thực dẫn, trong những lúc một trong những câu hỏi vô P.. vẫn chưa xuất hiện. Mặc mặc dù vậy trên đây vẫn là 1 trong quy tắc hữu ích.

Định nghĩa[sửa | sửa mã nguồn]

Một ngôn từ L là vô P.. nếu như và chỉ nếu như tồn bên trên một máy Turing vớ lăm le M sao cho

• Thời gian ngoan chạy của M là 1 trong nhiều thức của chừng lâu năm tài liệu vào
• Đối với toàn bộ x vô L, M mang lại thành quả 1
• Đối với toàn bộ x không tồn tại vô L, M mang lại thành quả 0

Các câu hỏi nổi trội vô P[sửa | sửa mã nguồn]

Xem thêm: xa ngoài kia nơi loài tôm hát

P bao hàm nhiều câu hỏi phổ cập, ví dụ như phiên bạn dạng ra quyết định của quy hướng tuyến tính, tính ước số cộng đồng lớn số 1, mò mẫm cặp ghép cực to, xác lập coi một trong những sở hữu nên số yếu tắc hoặc không^[2].

Quan hệ với những lớp khác[sửa | sửa mã nguồn]

P là 1 trong hội tụ con cái của NP (tập hợp ý những câu hỏi giải được vô thời hạn nhiều thức vì chưng máy Turing bất định). Mặc mặc dù không được chứng tỏ, nhiều Chuyên Viên tin cẩn rằng P.. là luyện con cái thực sự của NP.

P bao hàm NL, lớp những câu hỏi giải được vô không khí bộ lưu trữ vì chưng máy Turing biến động.

Xem thêm: bộ khoa học công nghệ

Ghi chú[sửa | sửa mã nguồn]