Bài toán mở, Toán ứng dụng và Tính toán, Nền tảng toán học, nêu năm 1971
Bài toán P đối NP
Gọi P là lớp bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức theo kích thước đầu vào, và NP là lớp bài toán quyết định mà lời giải đề xuất có thể kiểm tra trong thời gian đa thức. Câu hỏi là liệu P = NP: mọi bài toán kiểm tra được nhanh có luôn giải được nhanh hay không?
Tính đến năm 2026, P đối NP vẫn còn mở, và đa số nhà khoa học máy tính phỏng đoán P ≠ NP. Nhiều thập kỷ nghiên cứu đã tìm ra các rào cản hình thức — tương đối hóa (Baker–Gill–Solovay, 1975), chứng minh tự nhiên (Razborov–Rudich, 1994), và đại số hóa (Aaronson–Wigderson, 2008) — cho thấy toàn bộ các họ kỹ thuật chứng minh đã biết không thể tự mình giải quyết câu hỏi này, một phần lý do khiến tiến triển bị đình trệ dù đây là bài toán trung tâm.
Kết quả tốt nhất đã biết
- Chưa ai biết thuật toán thời gian đa thức cho bất kỳ bài toán NP-đầy đủ nào; thuật toán tốt nhất cho các bài như 3-SAT vẫn có độ phức tạp mũ trong trường hợp xấu nhất.
- Cận dưới về mạch chỉ được chứng minh cho các mô hình hạn chế (mạch đơn điệu, mạch độ sâu bị chặn), còn xa mới tới mạch tổng quát cần để tách P khỏi NP.
- Các kết quả rào cản (tương đối hóa, chứng minh tự nhiên, đại số hóa) cho thấy toàn bộ các họ kỹ thuật chứng minh đã biết không tự giải quyết được P đối NP.
Công cụ và chỗ dừng
| Công cụ | Đạt được | Chỗ dừng |
|---|---|---|
| Lập luận đường chéo và tương đối hóa | Tách được các lớp độ phức tạp yếu hơn (ví dụ định lý phân cấp thời gian) | Chứng minh được là không thể tự giải quyết P đối NP, vì câu hỏi này không 'tương đối hóa' (Baker–Gill–Solovay, 1975) |
| Cận dưới mạch tổ hợp | Chứng minh cận dưới mũ cho các lớp mạch hạn chế như mạch đơn điệu và AC0 | Rào cản chứng minh tự nhiên (Razborov–Rudich, 1994) cho thấy các kỹ thuật này không mở rộng được sang mạch tổng quát, nếu giả sử tồn tại bộ sinh giả ngẫu nhiên mạnh |
Câu hỏi còn mở
- P có bằng NP hay không?
- Nếu P ≠ NP, có tồn tại bài toán độ phức tạp trung gian thực sự giữa P và NP-đầy đủ hay không (định lý Ladner chứng minh chúng phải tồn tại, nhưng chưa ai tìm được ví dụ tự nhiên nào)?
Tài liệu tham khảo
- Stephen A. Cook (1971). The complexity of theorem-proving procedures
- Richard M. Karp (1972). Reducibility among combinatorial problems
- Stephen Cook (Clay Mathematics Institute) (2000). P vs NP Problem
- Alexander A. Razborov, Steven Rudich (1997). Natural proofs